HTW Berlin Fachbereich 4 Internationaler Bachelor Studiengang Internationale Medieninformatik (Bachelor) Info 2: Informatik II Summer Term 2023

Course Staff

Course Materials

Duane A. Bailey Java Structures. Data Structures in Java, for the Principled Programmer. Third (almost) edition. Free online textbook http://www.cs.williams.edu/~bailey/JavaStructures/

Thomas A. Standish Data Structures in Java, 1997, Addison-Wesley. Oldish - concentrates on the algorithms, not the fancy new stuff

Michael T. Goodrich and Roberto Tamassia Data Structures and Algorithms in Java in Java with CD-ROM. 5th edition, 2010. Wiley. The prices are atrocious, check if you can find one that is used or in the library. Some of the data structures and algorithms are described very well, others I find too complicated.

John R. Hubbard Schaum's Outline of Data Structures with Java (Schaum's Outlines) ISBN 0-07-136128-6. 2nd edition, 2009. This is a compact collection of samples and exercises.

Robert LaFore Data Structures and Algorithms in Java (Mitchell Waite Signature) ISBN-10: 1571690956, Sams, 2nd edition, 2002. Has a nice CD containing all of the examples, the animations look their age.

David Harel and Yishai Feldman Algorithmics. The Spirit of Computing. Addison-Wesley. 3rd edition, 2004. This is one of the classics of algorithmics. It has nothing whatsoever to do with Java, but explains Algorithmics nicely, with just the right amount of theory. The focus is on design and not maths.

Thomas Ottmann and Peter Widmayer Algorithmen und Datenstrukturen. BI Wissenschaftsverlag. 5th edition, 2012. Relatively thorough in the theory, but of course no connection with Java. It is in German, though.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms. 3rd edition. MIT Press 2009. (Algorithmen - Eine Einführung . Oldenburg. 2004) Big. Thick. Lots of math. No code. Yes, Rivest is the "R" in RSA.

Hans-Werner Lang Algorithmen: in Java - Sortieren, Textsuche, Codierung, Kryptographie. 3. Auflage. Oldenburg. ISBN 978-3486714067. 2012. The book is in German, unfortunately. But since the author as a Assistent in Kiel taught me Automata Theory, he gets special mention even though the book is rather heavy on the theory side. He does give many algorithms in Java, however, which makes them good for our purposes.

Aditya Y. Bhargava grokking algorithms: An illustrated guide for programmers and other curious people. Shelter Island: Manning. 2016. Very visual, very funny.

Donald E. Knuth The Art of Computer Programming Published Vol 1: Fundamental Algorithms, 1968 Vol 2: Seminumerical Algorithms, 1969 Vol 3: Sorting and Searching, 1973 Vol 4A: Combinatorial Algorithms, Part 1, 2011 Vol 4B: Combinatorial Algorithms, Part 2, 2022 Planned Vol 4C: Combinatorial Algorithms + Recursion, Part 3 Vol 5: Syntactic Algorithms Vol 6: The Theory of Context-Free Languages Vol 7: Compiler Techniques This is *the* classic algorithms book series found in all computing libraries.

Please don't get Weiss, Data Structures and Problem Solving using Java. It is a translation from the author's Pascal book and completely misses the mark in my opinion on the object-oriented way of thinking. Some of the others do too, to some extent or other.

Exercises are posted on the web site. There will be pre-labs that we expect you to have completed before you come to class.

Course Meetings

We lucked out this semester and have a great schedule. We meet for lecture every Monday and Tuesday at 12:15 in C 446. Labs will be in C 579 on Tuesdays, Group 1 at 14:00 and Group 2 at 15:45.

Please check the schedule each week—I sometimes have to reschedule on account of talks that I give.

Assignments and Grades

During the term, there will be 16 exercise sessions which will be written assignments on programming.

You must hand in at least 13 exercises in order to be admitted to the exam. We will be programming lots of "little" things about algorithms and data structures. There will be a 2-hour online examination on August 1, 2023 from 12:15-13:45 in C XXX and CXXX. The examination will cover data structures and algorithms and conceptual understanding in ways that may be difficult to assess during the laboratory sessions. You may take 2 hand-written pages into the exam with you—no computer-printed material. You may not leave the examination room after you have started the exam.

Your grade in Informatics 2 will be a weighted mixture of the following elements of the course:

• Examination: 60 %
• Laboratories: 45 %

I still use a "star" system for grading the exercise reports.

         
For the lab work you will receive a

• 45 points (i.e. a 1.0) if at least 14 are graded "****-" or "***--";
• 38 points (i.e. a 2.0) if at least 12 are graded "**---" or better;
• 31 points (i.e. a 3.0) if at least 10 are graded "*----" or better;
• 24 points (i.e. a 4.0) if you handed in at least 13 labs with a maximum of 6 labs graded "-----";
• 0 points (i.e. a 5.0) if you do not meet any of the above criteria.

Late work will not be accepted and will be treated as missing work. Always turn in what you have completed on time rather than delaying in the hope that you will be able to do more.

• Missing one laboratory will add 0.3 to your lab grade (i.e. lower your grade)
• Missing two laboratories will add 0.7 to your lab grade
• Missing three laboratories will add 1.0 to your lab grade.

If you are joining us from another program or are repeating the course, it may be difficult to get a position in the exercise group. If you want to do the exercises (and they will then count towards your final grade, register in LSF for the Nachbelegung. Otherwise, you are welcome to just register for the exam and it will count for 100 % of your grade. Speak with me. You are also welcome to come to the lectures, anyone may attend the lectures—and may get called on to explain something :) Only those who are regularly in the second semester have the right to be admitted to the exercise sessions—if they register normally.

Laboratory notes

Laboratory sessions are an essential part of the course. The laboratory assignments will be posted on the home page. You must work in pairs. We will be practicing pair programming with randomly chosen lab partners. You must report to the laboratory in time as you will be assigned to work with a different partner every week. You should be logged on before the lab starts. We will explain the exercise and you then have the rest of the first 10 minutes to discuss what you are going to do. To start with, one of you becomes the driver and will be typing, the other is the navigator, speaking over the driver's shoulder. After 20 minutes a bell will ring, and you switch places. The bell will ring two more times, and you switch each time. You will be exhausted after class, but you will have learned a lot! We only expect you to hand in a report about what you finished in class. You may, however, continue to work on the exercise at home with your partner of the week, if you wish.

There is a pre-lab/finger exercise section for all of the exercises. It is usually a good idea to think these through before coming to the lab. I expect each student to have their own pre-lab copy with them when they come to class. The report, however, will be for the pair, so there will only be one report for two people, although each hands in his or her own copy to Moodle. All lab work must be turned in on time and be labelled with the names of the students who did the work. They are in general due the evening before your next lab by 22.00 at the latest.

We want to have the assignments handed in as reports (in .pdf format only, please) explaining the process that you used in the lab. You should include your code in the appendix, but we want you to focus on what you as a pair tried, what failed, what worked. How did the pair programming proceed in this constellation? A screenshot of the results is expected, but should not make up the entire report. I expect the reports to be in complete sentences and to explain any collaboration (see below) that happened. Remember to put the assignment in the Moodle area and don't forget your names and matriculation numbers! Your report should include a reflection at the end on what each individual learned from this exercise. They should not be epic works, but about 5 pages per session, not including the code in an appendix. They can be written in English or German.

Late work will not be accepted. Any reports not handed in on time receive a zero. Always turn in what you have completed on time, rather than delaying in the hope that you will be able to do more.

Expectations and Policies

Missed Meetings

You are responsible for all material covered in each lecture unless otherwise indicated. This material may not be covered elsewhere, so if you miss a meeting, you are responsible for getting notes from a friend or otherwise making up the material. Handouts will not be distributed on paper, but will be made available on the course web site.

Attendance at laboratory is mandatory for those wanting a lab grade. If for any reason you cannot attend your scheduled laboratory session, it is your responsibility to make alternate arrangements with me as far in advance as is reasonably possible. In particular, if you have an athletic event or other scheduled conflict, I expect that you will discuss this with me as soon as the conflict is scheduled. I understand that unforseen events do arise (see below); however, your brother's wedding is (probably) not one of them.

The only exceptions to this policy (i.e., last-minute or after-the-fact rescheduling) will be in cases of significant and unanticipatable emergency. In these cases, I request a note from a doctor. In addition, I would appreciate it if you would make an effort to notify me at the earliest possible opportunity so that I can plan accordingly.

Collaboration

This section details the general course collaboration policy. Certain assignments require different kinds of, or restrictions on, collaboration. When the collaboration policy differs from that described here, it will be specified in the laboratory assignment.

I encourage you to work together on the exercises. They are designed for working in pairs, allowing you to help each other learn and to balance your knowledge and strengths. I expect that any written work you turn in will be done only by both of the authors of the notes, though it may reflect group preparation.

Experimental work is a more complex topic. It is often useful to discuss your program with peers or with me, and I strongly encourage this. It is particularly useful to do so as a means of debugging your program. Reading code written by others and having others critique your code are good ways to improve your programming style. However, it is of no benefit to you or to anyone else to have someone else actually do your experimental work. I expect that the default assumption (i.e., unless specified otherwise) is that experimantal assignments are your own work, but may reflect input from others just as an essay edited by friends might. You should be the one who wrote the code you turn in.

In each piece of work that you turn in, you must specify everyone with whom you have collaborated and each person's role in the collaboration (e.g., pre-lab, post-lab discussion and analysis, in-lab coding—specify which pieces or how responsibility was distributed—, debugging, or advice). Failure to specify such collaboration will be interpreted as a statement that you have not collaborated with others in your work. While this is acceptable under course policy, it is probably ill-advised. (Really. I want you to work together and to learn from each other!)

Examinations are diagnostic in nature and as a consequence should represent independent work.

Of course, copying of the work of others is entirely unacceptable and will result in the lab in question being marked as failed. This includes pre-lab work. Depending on the nature of the copying, there may be further penalties assessed.

Where to Find Additional Information

The primary source of information for this course is the world-wide web. The home page for the course is located at http://people.f4.htw-berlin.de/~weberwu/info2/. Course materials will be made available there. Check this site regularly for news and updates.