15-122Principles of Imperative ComputationSpring 2011Frank PfenningTom Cortina, Ananda Gunawardena, William Lovas, Karl Naden, Jacob PotterJason Chow, Jason Koenig, Sri Raghavan,Thomas Tuttle, Bill Zorn http://www.cs.cmu.edu/~fp/courses/15122-s111OverviewGoals of This CourseInteractionsLectures, Recitations, Office HoursAssessmentQuizzes, Homeworks, ExamsA Mysterious Function2GoalsComputational ThinkingAlgorithmsProgramming3Computational ThinkingSpecification vs. implementation; correctnessLogical vs. operational reasoningAbstraction and interfacesLoop and data structure invariantsReasoning about resource bounds4Programming SkillsTransformation of algorithmic ideas into correct imperative codeSpecify, write, test, debug, (re)factor code in the smallSome familiarity with Unix tools and C5Programming LanguageC0: a small safe subset* of Cint, bool, char, string, arrays, pointers, structsEssential algorithmic and programming ideasRelatively close to machine (imperative)Sound reasoning with contractsTransition to C near end of course6Algorithmic IdeasAsymptotic complexitytime/space/amortizedworst case/average caseimportant classes: O(1), O(log n), O(n log n), O(nk), O(2n)Divide-and-conquerSelf-adjusting data structuresRandomnessDynamic programmingEmphasis on imperative prog’s, ephemeral data struct’s7Concrete AlgorithmsBasic arithmeticBinary search, sortingStacks and queues, priority queuesBinary trees, dictionaries, maps, sets, triesHashing, hash tablesBinary decision diagramsGraph traversal, minimum spanning trees8Role in Curriculum15-150 Principles of Functional Programming15-213 Introduction to Computer Systems15-210 Fundamental Alg’s & Data Struct’s15-214 Principles of Software Systems9OverviewGoals of this courseInteractionsLectures, Recitations, Office HoursAssessmentQuizzes, Homeworks, ExamsA Mysterious Function10LecturesPlease be here, please be activeAsk and answer questions, pay attentionLecture notes after lectureLaptops for note-taking onlyNo surfing, email, games, ...Too distracting for everyone else11RecitationsReinforce lecture materialProblem solvingHow-to programming and tool supportGet to know your instructor12Office HoursWe like to see you!Any questions and issues with courseSee web page for current hours and locationCluster help available Mon-Thu 6:30-9:30!13On-line CommunicationBlackboard for grades, quizzes, email announcementsBboard cyrus.academic.cs.15-122Email to me, TA, or CACluster Linux machines for assignments14OverviewGoals of this courseInteractionsLectures, Recitations, Office HoursAssessmentQuizzes, Homeworks, ExamsA Mysterious Function15QuizzesTest basic understandingOn-line on Blackboard, auto-gradedDue at midnight(!) (see schedule on-line)8 quizzes, drop lowest scoreTotal of 7 * 15 = 100+5 pts16MidtermsTest functional understanding of materialDuring lecture period (80 mins)Closed book, closed laptop, 1 sheet of notesTotal of 2 * 100 = 200 pts17FinalTesting cumulative mastery of materialThree hours during final exam periodClosed book, closed laptop, 1 sheet of notesTotal of 250 points18AssignmentsWeekly assignment (see on-line schedule)Apply material in problem solving contextCombination of written and programmingHand-in start of lecture (written) & online (prog.)Total of 3 late days on prog, none on writtenMax of 1 late day per assignmentTotal of 7 * 50 + 1 * 100 = 450 pts19Academic IntegrityQuizzes, exams, homework must be your ownOK: discussion of course material, practice problems, study sessionsNot OK: copying or discussing answers, looking at or copying each others code (even parts)University policy will be applied rigorously!20OverviewGoals of this courseInteractionsLectures, Recitations, Office HoursAssessmentQuizzes, Homeworks, ExamsA Mysterious Function21Bug Report!22int f (int x, int y) { int r = 1; while (y > 1) { if (y % 2 == 1) r = x * r; x = x * x; y = y / 2; } return r *