DOC PREVIEW
CMU CS 15122 - syllabus

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Learning OutcomesProgramming LanguageCourse MaterialsStudent EvaluationSchedule15-122: Principles of Imperative ComputationCourse SyllabusFrank PfenningAugust 28, 2011This course is intended for students with a basic understanding of pro-gramming (variables, expressions, loops, arrays, functions). It teaches im-perative programming and methods for ensuring the correctness of pro-grams. Students will learn the process and concepts needed to go fromhigh-level descriptions of algorithms to correct imperative implementa-tions, with specific application to basic data structures and algorithms. Muchof the course will be conducted in a subset of C amenable to verification,with a transition to full C near the end. 21-127 Concepts of Mathematics is aco-requisite (must be taken before or in the same semester). This course is apre-requisite for 15-213 Computer Systems and 15-210 Parallel and SequentialData Structures and Algorithms.1 Learning OutcomesWe broadly categorize the learning outcomes into computational thinking,programming skills and data structures and algorithms.Computational ThinkingIn the area of computational thinking, students will be able to• Understand abstractions and interfaces.• Relate specifications to implementations.• Express pre- and post-conditions for functions and loop invariants.• Use data structure invariants.• Reason rigorously about code, both logically and operationally.SYLLABUS AUGUST 28, 201115-122 Principles of Imperative Computation 2• Analyze asymptotic complexity and practical efficiency.• View programs as data.Programming SkillsIn the area of programming skills, students will be able to• Understand the static and dynamic semantics of their programs.• Develop, test, rewrite, and refine their code.• Work with specifications and invariants.• Use and design small API’s.• Use and implement mutable data structures.• Render high-level algorithms into correct imperative code.• Write C programs in a Unix-based environment.Data Structures and AlgorithmsIn the area of data structures and algorithms, students will be able to• Perform asymptotic analysis on sequential computation, includingsimple amortized analysis and recognition of common complexityclasses (O(n), O(n ∗ log(n)), O(n2), O(2n)).• Apply the divide-and-conquer strategy in algorithm design.• Understand properties of simple self-adjusting data structures.• Effectively employ a number of basic algorithms and data structures,including binary search, subquadratic sorting, stacks and queues, hashtables, priority queues, balanced binary search trees, tries, binary de-cision diagrams, simple graph algorithms.SYLLABUS AUGUST 28, 201115-122 Principles of Imperative Computation 32 Programming LanguageIn weeks 1–11 the course uses C0, a small safe subset of C augmented with alayer texpression contracts. This language has been specifically designed tosupport the student learning objectives in this course. In particular it pro-vides garbage collection (freeing students from dealing with low-level de-tails of explicit memory management), fixed range modular integer arith-metic (avoiding complexities of floating point arithmetic and multiple datasizes), an unambiguous language definition (guarding against relying onundefined behavior), and contracts (making code expectations explicit andlocalize reasoning).In weeks 11–15 the course transitions to C, in preparation for subse-quent systems courses. Emphasis is on tranferring positive habits devel-oped in the use of C0, and on practical advice for avoiding the pitfalls andunderstanding the idiosyncrasies of C. We use the valgrind tool for propermemory management.3 Course MaterialsThere is at present no textbook for this course, but detailed lecture notes aswell as a programming language reference. Course materials can be foundat:• Fall 2010: http://www.cs.cmu.edu/∼fp/courses/15122-f10• Spring 2011: http://www.cs.cmu.edu/∼fp/courses/15122-s11• Current: http://www.andrew.cmu.edu/course/15-1224 Student EvaluationStudents will be evaluated based on the following components:• 8 Assignments (total 45%), each with a written and a programmingcomponent.• 1 Final (total 25%) of 180 minutes.• 2 Midterms (total 20%) of 80 minutes each.• 8 Quizzes (total 10%), taken on-line.SYLLABUS AUGUST 28, 201115-122 Principles of Imperative Computation 4A total course score of 90% and above is guaranteed an A, 80%-90% a B,etc. but grade cutoffs may be lowered based on the difficulty of exams andassignments. For students near grade boundaries, class participation andextra credit will be considered at the instructors discretion.5 ScheduleCourse schedule will vary somewhat from semester to semester; the fol-lowing is a sample schedule.• Week 1: Course overview, contracts, introduction to C0 (functions,statements, expressions, types)• Week 2: Modular arithmetic, arithmetic and bitwise operations, ar-rays, loop invariants.• Week 3: Linear and binary search, divide and conquer, asymptoticcomplexity.• Week 4: Sorting algorithms, mergesort, quicksort.• Week 5: Queues, stacks, linked lists, pointers, recursive types, datastructure invariants.• Week 6: Memory layout, recursion, Midterm Exam I.• Week 7: Unbounded arrays, amortized analysis, hash tables.• Week 8: Interfaces, priority queues, heaps, ordering and shape invari-ants.• Week 9: Restoring invariants, heapsort, binary search trees.• Week 10: AVL trees, rotations, program testing.• Week 11: Polymorphism, introduction to C, Midterm Exam II.• Week 12: Memory management (malloc/free), valgrind, generic datastructures.• Week 13: Virtual machines.• Week 14: Tries, decision trees, binary decision diagrams, sharing,canonicity.• Week 15: Graph algorithms (spanning trees, union-find).SYLLABUS AUGUST 28,


View Full Document

CMU CS 15122 - syllabus

Download syllabus
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view syllabus and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view syllabus 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?