Welcome to EECS/CS 281!Me: Sugih Jaminemail: [email protected]: 4737 CSEHours: Tue/Thu 3:00-3:45, Fri 3:00-4:00, and by appt.(but never right before lecture)Tel: +1 734 763 1583Prereqs: EECS 203 and 280. StrictGSIs and IA:• Brian Kirby (kirbyb)• TBD (): TBD• Christopher Peplin (peplin)GSI office hours will be held at the NE corner of the Dude 3rd flr.Sugih Jamin ([email protected])ReadingsRequired:• Preiss, Data Structures and Algorithms with Object-Oriented DesignPatterns in C++• Class handouts• Web site and Forum(!)Recommended:• Soulie, J., C++ Tutorial (online)• C++ stdlib and iostream Reference (online)• Sebern, string class (online)• Stroustrup, The C++ Programming Language, 3rd. ed.• Lippman and Lajoie, C++ Primer, 4th. ed.• Josuttis, The C++ Standard LibrarySugih Jamin ([email protected])Web site and ForumWeb site: http://irl.eecs.umich.edu/jamin/courses/eecs281/Forum (not up yet):• register first• DON’T use your CAEN passwd• either use your uniqname as the forum account or use your umichemail, so that we can verify membership• DON’T post solutions! (Honor Code violation)No: here’s my code, why doesn’t it compile/runNo: this problem can be solved using data structure X, or algorithm YIf in doubt, err on caution, and ask by emailSugih Jamin ([email protected])What 281 coversHow to build various tools from existing ones (data structures)How some tools are better for certain tasks than other tools(performance analysis)(“When you have a hammer every problem looks like a nail.” Not)How to go about solving a task using the tools (algorithms)How to improve the tools and solutions, andto hone your programming skillsSugih Jamin ([email protected])Data Structures and AlgorithmsData structures: collections of variables, possibly of different data types,connected in various waysAlgorithms: methods for solving problems that are suited for computerapplicationsAlgorithm + Data Structures = Programs [N. Wirth]Algorithmic Thinking: “Conceptualize problems with digital representationsand seeks algorithms that express or find solutions” – P.J. DenningSugih Jamin ([email protected])Discussion SessionMake sure you register for a discussion session!• W 3:30-4:30 2150 DOW• W 3:30-4:30 1003 EECS• F 1:30-2:30 1006 DOW(there will be NO discussion this week)Sugih Jamin ([email protected])Grading PolicyCourse grade composition:• Final: 20%• Midterm: 20%• Homeworks (HWs): 12%• Programming Assignments (PAs): 46%• Class Participation: 2%Four free late days (incl. weekends and holidays)You must keep track of your own late daysSugih Jamin ([email protected])Regrade• except for arithmetic error in grade computation,all regrade requests must be made in writing• must explain the technical reasons requiring regrade• must be made 5 working days after the work is returned to the class(except same day for final exam)• the whole work will be regradedSugih Jamin ([email protected])Cheating and CollaborationYou are encouraged to learn from each otherWe look forward to lively discussions in class and on the forumHowever, cheating is not tolerated andwill be reported to the Honor CouncilCheating is when you copy, with or without modification,someone else’s workIt is also considered cheating to knowingly expose your solutions orto use some other publicly available solutionsNOTE: It is also considered cheating to have a different algorithmimplemented than the one specified in the programming assignmentWhen in doubt, askSugih Jamin ([email protected])ExamsMidterm: Thu, Oct. 25th, 6:00-8:00 pmFinal Exam: Wed, Dec. 19th, 4:00-6:00 pmScheduling conflicts:• only documented medical or personal emergency allowed• if you need extra time to complete an exam due to personal disability,please inform us 1 week in advance• other scheduling conflicts will not be considered two weeks after thestart of the term (today)• outside commitments, e.g., job interviews, marching band trips,top-coder contests, are not considered valid reasons for missing anexamSugih Jamin ([email protected])AssignmentsHomeworks to be turned in hardcopy in the 281 lockbox in 2420 EECSProgramming assignments:• no group project• no STL• must not include external materials (e.g., open-source codedownloads) unless requested• must compile and run on CAEN’s Linux with the latest version of g++Put your uniqname on EVERYTHING you turn inDo NOT submit ANYTHING by emailSugih Jamin ([email protected])Programming Assignment GradingGrading criteria:• code compiles• code runs correctly• code runs fast• code is readable, well-documented, e.g.,o no use of literalso code re-use instead of cut-and-paste• algorithm is efficient• implementation is efficient, e.g.,o no unnecessary copyingo no loop invariant statement in loopSugih Jamin ([email protected])Magic ShowSugih Jamin ([email protected])Performance Analysis of Name SearchBest caseWorst caseAverage caseCommon case(What’s the difference between average and common cases?)Sugih Jamin ([email protected])Execution CostAlgorithms take resources to executeResources:• Space: memory, bandwidth• TimeTwo types of resource cost:• fixed cost• variable costSugih Jamin ([email protected])Space Time TradeoffIf you can load all your data into memory,you can sometimes come up with very fast algorithmWhere space matters:• handheld devices• embedded systems• large data-set problems, examples:Sugih Jamin ([email protected])Timing CostFixed cost (one-time cost):• coding time• compile time• variable initializations• etc.Variable cost:• run time: depends on the size of the problemSugih Jamin ([email protected])Runtimes of our name search problemAssume can search 10 names/msPopulation (size) Linear BinaryEECS 281 (100) 10 ms 0.7 ms (lookup 7 names)UM (40000) 4 secs 1.5 msWashtenaw 35 secs 1.8 msMI (9 mil) 15 mins 2.3 msUS (290 mil) 8 hours 2.8 msWorld (6 billion) 7 days 3.3 msImplication: there is usually more than one way to solve a problemWant: the most efficient waySugih Jamin ([email protected])Algorithm DesignTypical approach:• define problem to be solved• understand its complexity• decompose it into smaller subtasksAlgorithmic Thinking: “Conceptualize problems with digital representationsand seeks algorithms that express or find solutions” – P.J. DenningSugih Jamin ([email protected])Algorithm DesignTypical approach:• define problem