《算法设计与分析_第一次课》由会员分享，可在线阅读，更多相关《算法设计与分析_第一次课（135页珍藏版）》请在金锄头文库上搜索。
1、Design and Analysis of Algorithms Jun Han School of Computer Science BUAA Course Overview Administrative Details StaffStaff Lecturer: 韩军 Location: 北航新主楼 G 座 1112. Phone:8231 6340 Email: jun_han Profile: Your background I assume that you have substantial programming skills and Knowledge of Data struc
2、ture You need to be comfortable with basic concepts from Discrete Maths. About Algo. ? You Are Supposed to Be Cool minded Self motivated Programming addicted ? AND Your feedback is Valuable Course Representative and Tutors To Be Advised Course Outline This is NOT a first course in Algo. design and a
3、nalysis It is intended to provide the basis for competent design and programming algorithms with optimality You need to acquire not only theory but skills in designing, analysing and programming algorithms Syllabus Chapter 1Introduction Chapter 2 Complete Development of an Algorithm Chapter 3Sorting
4、，Searching and Matching Algo.s Chapter 4Divide and Conquer Chapter 5Dynamic Programming Chapter 6Greedy Algorithms Chapter 7 Backtracking Chapter 8Branch and Bound Chapter 9NP Completeness ( Knowledge; English in computer science; Your future work. *I will suppose you can understand; Languages (Prog
5、ramming) Whatever you like C+ Java Pascal Delphi VB Woo! Home Work and Assessment Overview During the semester there will be 3 home work question sheets and 3 programming assignments to help you to monitor your progress. Plan to work consistently! Your regular work gives me valuable evidence that yo
6、u can design and code an algorithm. Assessment Marks from these components and from your final examination will be combined to produce a single mark as follows: 30% (3 x 10%) for home works 30% (3 x 10%) for assignments 40% for the final examination (written, close book, close note) Attendance 0 to
7、-10 General instructions for assignments Please note very carefully the following points (applicable to ALL assignments). If you are not sure of the exact requirements, please ask. Include a comment at the start of your program indicating your name and student number. Include complete pseudo code an
8、d a flow chart of your program. Choose identifier names very carefully to convey the use of those identifiers. Ensure that the layout of your program statements follows a sensible indentation convention. Submit Source code and executable program Marks may be lost if you do not follow these requireme
9、nts. Assignment deadlines You are expected to schedule your work to meet deadlines - this is what happens in the real world. Also, it is simply not fair to other students who in most cases will have worked very hard, and perhaps have given up leisure activities in order to meet deadlines. Assignment
10、s: general advice For all assignments, use at least the given test data. Your program will be tested with this and some other data and it must behave at least as well as my version, which is by no means perfect. Examine the sample output for each program. From this it should be clear that you need t
11、o check for various error conditions. Getting to 1st base If your program fails to compile you will receive zero credit. Please also ensure that it runs as per the specification given. If you are not sure as to the exact requirements, please ask. More Legalities For this subject, as in all Computing
12、 Science subjects except where group assignments are organized, assignments must be substantially your own work. Submissions will be routinely scrutinized for similarity. Originality It is perfectly in order to discuss what the requirements are, or even to discuss your approach, but code must be you
13、r own for at least two reasons. You need the (sometimes arduous) experience of writing programs. We need to test your skills. Plagiarism If you copy from someone, or work very closely with a friend, we will probably detect it. When we do, you will be penalized. You should familiarize yourself with t
14、he university rules regarding plagiarism. Anything left? Design and Analysis of Algorithms Introduction What is an algorithm ? Algorithms An algorithm is a set of instructions for performing a task. It must have the following features: Each instruction must be clear and executable. The next step mus
15、t be determinate. The process must terminate. The goal must be achieved. Examples of algorithms are: a recipe. a musical score. a knitting pattern. Features of Algorithms Each algorithm has an author and a static form. Upon execution by a processor, we have a dynamic process. The processor for a rec
16、ipe is a cook, for a musical score is a performer. Algorithms: Declarations Objects are manipulated. Programs operate on data. Instructions may be preceded by a declaration of the objects involved. This is true of recipes, model aeroplane assembly It is also true of many modern programming languages. Algorithms: Decisions Instructions are executed sequentially. Decisions may be requir
