15-210
source link: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Announcements
- Final Exam: Mon May 14, 5:30 — 8:30pm, GHC 4401 (Rashid). Practice final is now available. Review Session: Sunday May 13, 7pm also in GHC 4401.
- Assignment 9 has been posted.
- Assignment 8 has been posted.
- Midterm II: Thu Apr 5, 7 — 8:20pm, WeH 7500. Practice midterm II is now available.
Overview
This course aims to teach methods for designing, analyzing, and programming sequential and parallel algorithms and data structures. The emphasis is on teaching fundamental concepts applicable across a wide variety of problem domains, and transferable across a reasonably broad set of programming languages and computer architectures. The course, however, includes a significant programming component in which students will program concrete examples from domains such as engineering, scientific computing, graphics, data mining, and information retrieval (web search). Unlike a traditional introduction to algorithms and data structures, this course puts an emphasis on parallel thinking—i.e., thinking about how algorithms can do multiple things at once instead of one at a time. The course follows up on material learned in 15-122 and 15-150 but goes into significant more depth on algorithmic issues.
The concepts covered by this course include:
- Problem vs. Algorithm: A problem defines an interface (e.g., sorting) while an algorithm defines a particular method to solve the problem (e.g., quicksort). Being able to cleanly define a problem is key in the process of putting together large programs and in reusing their components. We cover a variety of fundamental problems (sorting, minimum spanning tree, nearest neighbors, ...) and a variety of algorithms for solving them (quicksort, Dijkstra's algorithm, ...).
- Asymptotic Analysis: Although the so-called big-O analysis is not going to accurately predict wall-clock time, it is critical for getting a rough estimate of the performance of an algorithm and helping guide algorithm design and selection. In the class, we analyze performance in terms of work, span and space. We cover a variety of techniques for analyzing asymptotic performance including solving recurrences, randomized analysis, and various counting arguments.
- Techniques in Algorithm Design: There are just a few techniques that play the key role in the the design of most parallel/sequential algorithms and data structures. In this class, we cover these techniques, including using collections (sets, sequences, priority queues, ...), divide-and-conquer, contraction, the greedy method, balanced trees, hashing, sparse matrices, and dynamic programming.
Course Information
Lectures:
Tue and Thu 12:00-1:20pm, WeH 7500Recitations:
Section A - Wed 10:30-11:50, MM 103Section B - Wed 11:30-21:20, PH A18B
Section C - Wed 12:30-1:20, WeH 5302
Section D - Wed 1:30-2:20, WeH 5302
Textbook:
There is no course textbook. Course notes will be provide instead. As we may not be able to cover all the material during lectures, please read the notes for additional background and further details.Grading:
45% Assignments30% Midterms
25% Final
Policy
Late Assignments
Homeworks are due at 11:59PM US Eastern Time unless otherwise noted on the assignment.
Your homework will be considered 1 day late if it is handed in within 24 hours after it is due and 2 days late if handed in within 48 hours after it is due. You are permitted a budget of FOUR (4) late days per semester at no grade penalty (e.g. you might use 2 on 1 assignment, and 1 each on two other assignments). At most TWO (2) late days may be used per assignment. If you have used up these four late days, your score will be reduced by 25% off of the total (not your score) per late day. Except in extraordinary circumstances, no late homework will be accepted beyond the late date.
Electronic devices during class
As research on learning shows, unexpected noises and movement automatically divert and capture people's attention, which means you are affecting everyone's learning experience if your cell phone, pager, laptop, etc. makes noise or is visually distracting during class.
For this reason, we ask you
- to turn off the sound on your electronic devices, and
- to sit in the back row if you plan to use your laptop.
Academic Integrity
All students are expected to be familiar with, and to comply with, the University Policy on Cheating and Plagiarism.
Any work submitted as a homework assignment or examination must be entirely your own and may not be derived from the work of others, whether a published or unpublished source, the worldwide web, another student, other textbooks, materials from another course (including prior semesters of this course), or any other person or program. You may not copy, examine, or alter anyone else's homework assignment or computer program, or use a computer program to transcribe or otherwise modify or copy anyone else's files.
To facilitate cooperative learning, it is permissible to discuss a homework assignment with other students, provided that the following whiteboard policy is respected. A discussion may take place at the whiteboard (or using scrap paper, etc.), but no one is allowed to take notes or record the discussion or what is written on the board, and you must allow four hours to lapse after any discussion before working on the assignment. The fact that you can recreate the solution from memory is taken as proof that you actually understood it.
We may sometimes run automatic code comparison programs (such as MOSS). These programs are very good at detecting similarity between code, even code that has been purposefully obfuscated. Such programs can compare a submitted assignment against all other submitted assignments, against all known previous solutions of a problem, etc. The signal-to-noise ratio of such comparisons is usually very distinctive, making it very clear what code is a student's original creative work and what code is merely transcribed from some other source.
Recommend
-
48
-
177
Course Overview Wireless Attacks (PEN-210) introduces students to the skills needed to audit and secure wireless devices. It’s a foundational course alongside PEN-200
-
6
Episode 210: The Elephant in the Room ...
-
17
Sending Email with SMTP4Dev and MailKit (#210)136 views•May 10, 2021 ...
-
7
About PaulaDr. Paula Caligiuri is a D’Amore-McKim School of Business Distinguished Professor of International Business at Northeastern University, and lives in Boston, Massachusetts....
-
10
Blockstream Raises $210 Million, Now Valued At $3.2 Billion – HodlalertBlockstream Raises $210 Million, Now Valued At $3.2 Billion Bitco...
-
11
Episode 210 – Compiler API with Jason BockPodcast: Play in new window |
-
6
Episode 210 210 - What We Wish We Knew We're old. That means you should totally take advantage of a...
-
3
Zaraye获得210万美元融资,老虎基金领投2022/04/18 21:52|作者
-
8
这里记录每周值得分享的科技内容,周五发布。 本杂志开源(GitHub: r...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK