15-122Principles of Imperative ComputationFall 2010Frank PfenningTom Cortina William Lovashttp://www.cs.cmu.edu/~fp/courses/15122-f101OverviewGoals 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/parallelworst case/average caseimportant classes: O(1), O(log n), O(n log n), O(nk), O(2n)Divide-and-conquerP vs NP [recently in the news!]Emphasis on imperative prog’s, ephemeral data struct’s7Concrete Algorithms(sample, not a promise)Basic arithmeticBinary search, sortingStacks and queues, priority queuesBinary trees, dictionaries, maps, sets, triesHashing, hash tablesGraphs, reachability, shortest path, spanning treesSatisfiability (SAT)8Role 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 attentionNo textbook, new course, ...Laptops 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 Tue & 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 and /afs for assignments14OverviewGoals of this courseInteractionsLectures, Recitations, Office HoursAssessmentQuizzes, Homeworks, ExamsA Mysterious Function15QuizzesTest basic understandingOn-line on Blackboard, auto-gradedDue Monday night(!)8 quizzes, drop lowest scoreTotal of 7 * 15 ≈ 100 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 (out Thu, due Thu)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)Tomorrow in recitation: read and sign academic integrity policy for this class; ask when in doubtUniversity policy will be applied rigorously!20OverviewGoals of this courseInteractionsLectures, Recitations, Office HoursAssessmentQuizzes, Homeworks, ExamsA Mysterious Function21Bug Report!22int f (int n) { int i = 0; int k = 0; while (k <= n) { k += (i<<1) + 1; i++; } return
View Full Document
Unlocking...