Algorithms for Systems EngineeringIE 172 — Spring 2010Instructor: Pietro BelottiMohler Lab 322Phone: 610-758-3865Email: [email protected] page: http://coral.ie.lehigh.edu/˜belotti/?page id=914Meeting: Monday, Wednesday, Friday, 9:10am – 10:00am, Mohler 453Lab: Tuesday, 1:10pm – 4:00pm, Mohler 444Office hours: Monday and Wednesday, 3:00pm – 5:00pm, or by appointment.Prerequisites: CSE 17 and ENG 1.EvaluationProblem sets: 25%Lab: 25%Midterm: 20%Final exam: 30%Both the midterm and the final exam will be taken in class, and will beclosed notes, closed books. They will consist of a set of simple problems onthe analysis of algorithms.GradingPercentage ≥ 93 ≥ 88 ≥ 83 ≥ 78 ≥ 74 ≥ 68 ≥ 62 ≥ 55 ≥ 50 ≥ 45 ≥ 40 ≥ 0Grade A A- B+ B B- C+ C C- D+ D D- FScope of the courseCountless problems in Engineering are solved with software packages of var-ious size. At the core of any software package is a set of data structures andalgorithms that are the result of an accurate analysis of the problem. This coursefocuses on the most important data structures and algorithms for solving prob-lems in Engineering. You will learn to analyze a certain problem in Engineeringand to choose the proper data structure and algorithm for solving it. All lab ac-tivities will be conducted in the C++ programming language.Course materialThe textbook for this course is:Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, CliffordStein. Introduction to Algorithms, Second Edition (McGraw-Hill, 2003).Each lecture of the course will focus on one or more chapter of this textbook,which you are suggested to read. Three other very interesting books, providingexamples and insights, are the following:– Donald Knuth. The Art of Computer Programming (Addison-Wesley);– Robert Sedgewick. Algorithms in C++ (Addison-Wesley);– David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing (Add-ison-Wesley).Needless to say, the Web is full of resources on algorithms, data structures,programming languages, and implementation tricks. You are encouraged to ex-plore the online material and to get inspiration from it when you develop yourown algorithm — after all, this is how most algorithm developers work. How-ever, you must refer to them for inspiration only, cite all the resources you haveused, and never copy any material without citing it properly. Failure to followthis policy will have very serious consequences on your final grade.Calendar (subject to change!)Week Block Topic Reading Laboratory1 Introduction Intro and C++ Review Chapters 1-2 Eclipse2 Analyzing Algorithms Chapter 3 Search3 Recursion, recurrences Chapter 4 Selection4 Sorting Heaps and Quicksort Chapters 6-7 Stacks, Queues5 Searching Binary Search Trees Chapter 12 Sorting6 Hash Tables Chapter 11 Binary Search Trees7 Review Hash Tables8 Networks Graph Algorithms Chapter 22 Midterm9 Shortest Paths Chapter 24 Shortest paths10 Min. Spanning Trees Chapter 23 Graph Search11 Numerical String Matching Chapter 32 Shortest Paths12 Cryptography Chapter 31 String Matching13 Matrix Operations Chapter 28 Cryptography14 Systems of Equations Chapter 28 ReviewProblem sets and labsEvery week, a lab session of about three hours will focus on notions learned inthe previous lectures. Each student is required to solve an Engineering problemby designing and implementing proper data structures and algorithms. At theend of the lab, the resulting code must be emailed to me for evaluation. A prob-lem set related to the lab problem has to be solved afterwards and the resultmust also be emailed to me, before the beginning of the next lab. Note: prob-lem sets will be penalized of 50% for each day they are late. After two days,they will not be accepted. No exception.Online resourcesAnnouncements and messages will be posted on the course website. Lecturenotes, course information, homeworks, solutions, and other material will alsobe posted on the course webpage, while grades will be posted on Blackboard.PolicyYou are expected to come to class regularly and to be prepared for each class byreading the relevant sections of the textbook ahead of time. I will post slides inadvance so that you may bring them to class if you wish. You are also expectedto participate in class discussions and ask questions when you are confused.Plagiarism: I encourage you to consult with your colleagues when you’re work-ing on homework. However, you will not understand the material or do wellon the exams unless the work that you turn in is ultimately your own. There-fore, you must write up your answers alone, and without looking at anythingyou wrote down while working with your group. This means that if you solvedthe problem with a friend, you’re going to have to go home and solve it all overagain, by yourself. The work you turn in must be your own.You must cite everyone with whom you worked or consulted about eachproblem, as well as any material (books and online resources other than thecourse books and lecture notes) that you used to solve the problem. Any breachof this policy will be considered an act of plagiarism, and no credit will be givenfor such assignments. Repeat offenses will be grounds for failure for the course.Extended Absences: If you believe you will miss two or more consecutive lecturesdue to illness, family emergencies, etc., please contact me as early as possibleso that we can develop a plan for you to make up the missed material. Underno circumstances will I give credit for missed homework or exams unless youhave discussed your absence with me in advance.See also http://www.lehigh.edu/˜inprv/academicintegrity.html.Voice/video recordingAny voice or video recording device may be used only with the approval ofall participants of the given course. I will ask, at the beginning of the course,if any of you intends to use any means of voice or video recording in class.I personally have nothing against that, but if anybody opposes the recording,then it is illegal to use such devices. Any student should let me know, either inclass or by email, at any time during the course, if he/she does not consent therecording.Accommodations for Students with DisabilitiesIf you have a disability for which you are or may be requesting accommo-dations, please contact both your instructor and the Office of Academic Sup-port Services, University Center C212 (610-758-4152) as early as possible in thesemester. You must have documentation from the Academic Support Servicesoffice