Programming In Engineering

Algorithms and Scientific Programming series: Lecture 2 Agenda 1 hour Victor Miclovich November 16, 2009 Today’s session might be our last this year... but the good thing is that you are all getting the hang of things and programming in Python. Learning to become good developers is the eventual goal of this ”program”. These are things I shall expect from you after the holidays: 1. Commitment (there won’t be room for sloppiness or reviews of previous work early next year ) 2. Do all the assignments and readings that I shall still be sending you weekly 3. Program! Meet S60 phone owners in this research group and do the programs in the book I left. This by the way is the lab experiment of this course. Because of our limited resources, we can’t always have phones around... I prefer to use a real phone and not an emulator. What are the advantages of having a real phone? • You will have real time analysis of output like messaging • The audio API is nice on a real phone • sockets libraries are used to connect to the Internet. I want you be able to take an image with using the camera api and be able to create services that can upload images either via a TCP stream or urllib module (this is part of the limited edition of PyS60 • If you still want to use the emulator go ahead... but trust me, the best experience is with a real phone. We shall use emulators sometime in the future... Also, try to program your phone using a bluetooth console... you can send python files to your phone via bluetooth; install the files as ”python scripts” Note: I mention ”python scripts” not ”python lib modules”...

1

Reading list: 1. Algorithms (sources: include Wikipedia, check out the University library, etc. + some occasional notes on the subject that I might send once in a while) 2. Computer networks... (sources: the CCNA forums, website, etc. also use Google ;) ) 3. Mobile technology... (sources: http://forum.nokia.com, blackberry website, anything that will give you information on the mobile/cellular/telecom industry) At the end of this... preferably after 1st January 2010, I will give you research questions for a report you are to write in two weeks... So, I expect you to keep notes on what you read. Not doing this implies that you might not be as reliable and efficient to continue with this research group. These are prerequisites for this research... I also want to warn you that MATHEMATICS flows in every topic that I have listed... just thought you should know, don’t be scared. I will give you a format on how to report research findings... it will also be nice to do this as a group, but hand in different reports; I will design a ”probability” program (or atleast pseudo-random) that will assign you separate topics that you will write about in those 2 weeks. Aim of this assignment The aim of this assignment is to test the following: • collaboration between members of the team • organization of the team • Development of certain methodologies of best practice as engineering teams • Can you be serious? The daily assignment is writing as many programs as you can in any language of your choice1

1

Problems in Algorithms

1.1

Sorting

In today’s lecture I shall do the following the traditional way: on a chalk board. • Insertion sort 1

preferably Python

2

• Merge sort • Asymptotic analysis

1.2

Complexity

Imagine a scenario where you have just come up with a recipe or algorithm to shorten an engineering process be it reduction in time of churning some cream in factory, or optimizing the way a circuit sends signals, etc. I remember telling of you some algorithms that we are to use and enhance • synchronization algorithms (the phone keeps sending data to a database before transferring it over a strong connection to a database/repository) • Multi-modal transfers • Packetization: breaking up large data into segments that are queued up before transfers across packet/cellular networks while using a background service to constantly check for cellular coverage These are all algorithms... we shall initially look at naive algorithms then work our way up to advanced algorithms. Why? Everything from the User interface in a phone to basic phone utilities/services in a development environment are all similar worldwide; we use known design patterns and procedures in development, but what makes a product different from the rest? I think you can guess the answer: It’s performance. Performance lies in the design of algorithms and their analysis. Application development steps in my ”sketchy” way: 1. Problem: everything in development starts with a problem that needs a solution 2. Requirements engineering: the next logical step is to analyze that problem which could involve lots of things from surveys, interviews, etc, then draft some kind of document... I think it is called a request for proposal or something like that 3. Design an Information architecture: this is just like designing a user experience; the big question here is to look at the context where this application will be used, and write up stories called user stories about how the experience should proceed.... (isn’t that an algorithm?) 4. Build a prototype: building this also requires another analysis and requirements gathering stage... it is not wise to do every requirement gathering as a fast step... in my own opinion I prefer that you iteratively gather requirements from your user and add features to every 3

stage of development or/and product... here you actually meet the tech needs... like what kind of networks is your app going to work on, how is it going to send data upstream2 , how is the app going to use the phone’s resources to connect to a service, etc 5. A step inside every other step: this is a crucial step... it happens in the previous steps too and designs it’s own bullet point :) Documentation is what makes the product... so within every step we document everything from our source to other scraps of paper we might be using 6. The forever loop: every product isn’t 100% efficient... we shall always keep refining the existing application... and if the worst case is to come, create it from scratch... 7. Next step is... Go to step one! What is the complexity this section is about? This section is about how you determine the efficiency of an algorithm? Wow! Then what kind of efficiency are you talking about?: Well, the efficiency could mean speed at which something gets done, it could mean how well limited resources are used (amount of CPU, memory and disk usage). The whole deal is to know whether an algorithm does the right thing the right way when given an input. Generally, complexity is a measure of the amount of a particular resource required to perform a given function.

1.3

Big-O notation

Complexity of an algorithm is defined in terms of the order of magnitude of the number of operations required to perform a function. • 0(1) denotes a function that runs in constant time • O(n) denotes a function that runs in linear time • O(n2 ) denotes a function that runs in quadratic time • O(log n) denotes a function that runs in logarithmic time • O(n log n) denotes a function that runs in time proportional to the size of the problem and the logarithmic time • O(n!) denotes a function that runs in factorial time • etc. 2

this means sending data to a server

4