Lecture notes for 08/26/97: Welcome to 15-211 Avrim Blum -- intros 4 Handouts -- admin * Course info -- what 211 is about * Lab 1 -- an example * C++ styleguide * C++ info INTROS: Course staff: Seth Goldstein and I will be switching off teaching lectures and doing sections. Also teaching sections have 3 TAs: Carl Burch, Craig Damon, Sam Perman. A change you'll be happy about: Since those of us teaching remember when we were undergrads we couldn't pay attention to 80 min straight of anything, we will only use 1st 60 min of scheduled lecture time: 12-1. RECITATIONS: Monday and Wednesday. Recitations will go through examples of topics discussed in lecture AND new material. You will be responsible for what's covered in section. Everyone should be assigned a recitation. If you can't make your section and need to switch, CONTACT INSTRUCTOR OF SECTION YOU WANT TO GO TO (e.g., by going to their section) and if not too full, they'll let you in. Briefly: Main focus of this course on how to take a problem you want to solve using computing - break it into pieces - work out an algorithm or method for solving it - and then turning that into a fast and correct program. Going to be doing this using the C++ programming language. We will be assuming you know C or C++. If you do not know either, you should expect to have to put in extra time getting up to speed. For those of you who know C but not C++, C++ is essentially a superset of C. We will be introducing C++ features as they become useful for what we're trying to do. The course is not about the intracacies of C++. The course is really about using computing to solve problems, and C++ happens to be a good language for doing this. Now I'm going to spend some time going over a few things in the COURSE GUIDE. You should read it more carefully at home. Handouts available electronically from Web page: /afs/andrew/scs/cs/15-211/www/home.html Last item on page: CLUSTER HELP One thing about programming is that its easy to have program that's mostly right except for some sneaky bug that you can be pulling your hair out sitting for hours trying to find. To try to alleviate this, we're going to have course staff in 5th floor cluster who will be right there to help you out, before hwks are due. TEXTBOOKS - Standish: Data Structures, Algorithms, and Software Principles in C. (I think Standish is particularly nice -- good description of algorithms AND programming) - Pohl: C++ for C Programmers (Optional: if you already have a C++ book, that's fine. If not, we recommend this one.) GRADES Formal requirements: 7 hwks, 3 quizzes, 1 midterm and 1 final. Out of 7 hwks and 3 quizzes (10 total) we'll drop lowest. Drop 1 quiz OR 1 hwk. PLease don't blow off a quiz AND a homework. Hwks will be about every two weeks. We'll hand out hwk1 on Thurs. Also, one LAB. Lab will introduce you to software we're using in the course. Completing and handing it in is required, but no points. Next page: more detailed schedule. ASSIGNMENTS Assignments will be handed in ELECTRONICALLY. Instructions in course info guide and on lab1. One thing you'll notice is that electronic handin is due at 11:59PM on Sunday night. Programming is sort of thing that doing when groggy at 4:00 in morning is not useful. If not done by midnight, either hand in what you have, or get some sleep and hand it in late. You can hand in up to 11:59pm Tues (2 days after) with a 20 point penalty. In any case: good idea to start work on it early. Give Extra Credit if 3 days early. E.C. handled separately from regular credit. At very end, we set cutoffs and use EC as one criteria for deciding whether to move up people just below a cutoff. It's not enough for programs to work. Part of grade is also based on style: readability, how well organized, etc. If you want to know why, just wait until Jan 1, 2000.... CHEATING POLICY Basically, following are OK: giving general C++ help, or in using debuggers, or discussing together code we hand out to you is fine. Helping other people find the bug in their code is fine. Even discussing the high-level idea of how you're going to attack a problem is fine, though you shouldn't give the whole thing away. -- But, what you hand in should be your own work. Copying other people's code is cheating. Copying other people's code and changing the variable names is still cheating. Besides, if you don't understand the assignments, you're not going to do very well on the tests. We do have a program that we run that compares assignments to look for copying, and it's pretty good though sometimes it's easier than that. Bottom line is: don't do it. It just causes both of us a lot of aggravation. If you're confused: SEE ONE OF THE COURSE STAFF. We're happy to help out. One last thing: If you have questions, can ask in lecture, recitations, office hrs, course staff in clusters, but also: BBOARDS:... cmu.cs.class.cs211.announce, cmu.cs.class.cs211.discuss announce: for us to get information to you. Make sure to read. Corrections, important announcements. discuss: good if you have a question - maybe something vague in hwk, or having some kind of difficulty. We'll be monitoring these frequently, but you're also encouraged to answer each other's questions. WHAT COURSE IS ABOUT. How to take a problem you want to solve, and come up with good high level approach or algorithm for solving it, go from there to good program -- fast, correct, easy to modify, and so forth. TALKING ABOUT: - take problem & break down into smaller tasks. - select good representation of data -- using data structures. - algorithm design: finding fast, correct method to solve. - analysis: show it's correct, understand whether scales well. - Turning this into code that's understandable, extendable, bug-free. Engineering parts: 1st 3, math parts (4 ,2,3). English parts: 5. Just like in English writing, notion of good style. Includes things like: -- modularity: separating code into understandable chunks. -- abstraction: hiding implementation details. -- documentation A PROBLEM THAT INCORPORATES SEVERAL ISSUES WILL BE DISCUSSING THROUGHOUT COURSE. Maybe you've seen at some airports or hotels they have machines where you type in where you want to get to and they give you instructions on the shortest way there. Say you wanted to do the same for CMU. User types in some place like STATION SQUARE. Want to give the shortest path to there -- Forbes - 5th - Pkway - Smithfield bridge -- SSQ. Couple main parts to this. --> Want to (A) Store map in a reasonable way in the computer, then (B) do some computing to figure out paths, and (C) store the results in a way it can be quickly recovered. all related: A and B: how you store <--> what kinds of algs can do. B and C: what kinds of results <--> what alg to use. First look at something simpler. small map. -- for simplicity say only going to ask to go to intersection. So, can number them -- say no turning restrictions. (A): This kind of picture is something called a "graph" (directed graph since 1-way streets) talk about near end of course. Store info using an "ADJACENCY LIST" representation. ARRAY, one elt per intersection. Store a list of which others are neighbors can get to and other info. What I want to talk about now is (C). Somehow we find shortest paths. We'll talk about (B) later in course. How can we store this information in some nice efficient way? EG: Say in big map, find shortest path from CMU to every point in PGH. EG: Big map: 18000 intersection, 25000 segments, avg dist over 40 segs. Might think need to store 18000 X 40 pieces of information. But turns out can do a lot better. Suppose I told you: to get to pt 13, last place you visit is 12. AND I told you what the shortest path was to 12. What is the shortest path to 13? If path to X has second-to last Y, uses shortest to Y. This means we can describe ALL the shortest paths by just ONE TREE, called the "shortest path tree (from point 0)". Store really compactly in "parent" or "prev" array. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ------------------------------------------------------------ 0 0 0 1 2 1 0 6 9or3 12 2or6 7 11 12 Say want to get to 11, how to read off? 11 <- 7 <- 6 <- 0 9 <- 12 <- 11 <- 7 <- 6 <- 0. So, only store one piece of info per point, not whole path.