Michael0x2a/cse-143-16au-study-guide.md

How to study

Programmieren ist zu einem großen Teil angewandte Problemlösung und nicht Auswendiglernen.Das bedeutet, dass man sich am besten auf Programmierprüfungen vorbereitet, indem man sich nicht hinsetzt und die Folien durchliest, sondern indem man viele Probleme löst.

Infolgedessen empfehle ich Ihnen dringend, sich wie folgt vorzubereiten:

  1. Versuchen Sie, mindestens 3 bis 4 Programmierprobleme pro Tag durchzuarbeiten, und zwar ab sofort.

    Bis zur Prüfung sind es noch etwa 12 Tage. Wenn Sie 4 Probleme pro Tag bearbeiten, werden Sie bis zur Prüfung etwa 30-50 Probleme gelöst haben, was Ihnen einen RIESIGEN Vorteil gegenüber Leuten verschafft, die in letzter Minute lernen. Wenn Sie einen sehr vollen Terminkalender haben, sollten Sie zumindest versuchen, 1 Problem pro Tag zu lösen.

    Das liegt zum einen daran, dass Sie viel mehr Erfahrung mit dem Lösen von Problemen haben als Leute, die in letzter Minute pauken, und zum anderen daran, dass wir manchmal einfach Probleme aus der Praxis für die Abschlussprüfung wiederverwenden. Wenn Sie 30-50 gelöste Probleme im Kopf haben, ist die Wahrscheinlichkeit, dass Sie in der Prüfung auf ein „Freebie“ stoßen, viel höher…

    Auf diese Weise haben Sie auch Zeit, Fragen zu stellen, wenn Sie auf Probleme stoßen, die Sie nicht lösen können.

    Versuchen Sie, jeden Tag eine Stunde in Ihrem Kalender einzuplanen, in der Sie sich nur hinsetzen und die Probleme durcharbeiten wollen. (Beginnen Sie außerdem früh mit HW 8, um sicherzustellen, dass Sie genügend Zeit haben, um sowohl zu lernen als auch Ihre HW zu bearbeiten).

  2. Planen Sie einen Tag ein, an dem Sie sich hinsetzen und eine Reihe von Problemen aus einem Rätselthema durcharbeiten.

    Sie sollten versuchen, so weit zu üben, dass Sie die Rätselprobleme zuverlässig und mit 100%iger Genauigkeit lösen können. Es kann produktiver sein, sich an einem Tag hinzusetzen und einen Haufen auf einmal durchzuarbeiten, damit man üben kann. (Versuchen Sie zum Beispiel an diesem Wochenende, eine Reihe von Polymorphismusaufgaben zu lösen.)

  3. Versuchen Sie, die Übungsaufgaben in einem Zug zu lösen. Nicht „editieren und neu kompilieren“.

    In der Abschlussprüfung wirst du keinen Compiler haben, der deine Arbeit überprüft. Geben Sie Ihr Bestes, um die Aufgaben beim ersten Versuch zu lösen. Benutzen Sie Bleistift und Papier, um die Probleme zu durchdenken, bevor Sie auf den „Absenden“-Knopf drücken.

    Wenn Sie die Übungsaufgaben nicht zuverlässig beim ersten Versuch richtig lösen, bedeutet das, dass Sie noch viel mehr üben müssen.

    (Das heißt, dass Sie sich am Anfang vor allem darauf konzentrieren sollten, die Aufgaben richtig zu lösen.

    Wenn Sie sich mit einem Thema relativ gut auskennen, sollten Sie sich darauf konzentrieren, die Aufgaben beim ersten Versuch richtig zu lösen.)

  4. Führen Sie eine fortlaufende Liste von „Dingen, die Sie verbessern müssen“.

    Wenn Sie einen Fehler machen, etwas übersehen oder bemerken, dass Sie verwirrt sind, schreiben Sie es auf.

    Nutzen Sie Ihre fortlaufende Liste von Fehlern, um sich daran zu orientieren, mit welchen Problemtypen Sie Schwierigkeiten haben und was Sie mehr lernen müssen.

    Sie könnten zum Beispiel feststellen, dass Sie manchmal Übungsaufgaben falsch lösen, weil Sie vergessen haben, eine Ausnahmeprüfung hinzuzufügen. Das könnte ein Hinweis darauf sein, dass Sie bei der Abschlussprüfung besonders vorsichtig sein sollten, was das Lesen der Anweisungen angeht.

    Oder Sie könnten feststellen, dass Sie Schwierigkeiten mit verknüpften Listen haben, bei denen Sie zwei verknüpfte Listen überarbeiten müssen. Das könnte eine gute Sache sein, um einen Lehrer um Hilfe zu bitten.

  5. Produktives Ringen ist gut; unproduktives Ringen ist schlecht.

    Es ist normal, bei der Arbeit an Problemen zu ringen. Versuchen Sie jedoch, „produktiv“ zu kämpfen, nicht „unproduktiv“. Wenn du an einem Problem arbeitest und das Gefühl hast, dass du stetige Fortschritte machst (auch wenn sie langsam sind), dann ist das „produktives“ Ringen.

    Wenn du jedoch feststeckst und zufällige Änderungen vornimmst, um zu sehen, ob sie funktionieren, dann ist das „unproduktives“ Ringen. Wenn Sie die „unproduktive“ Phase erreicht haben, sollten Sie das Problem beiseite legen, eine Pause einlegen, versuchen, an einem anderen Problem zu arbeiten, jemanden um Hilfe zu bitten usw.

Sammlungsprobleme

Binärbaum-Traversal- und Einfügeprobleme

Hier finden Sie einige Übungsprobleme: http://practiceit.cs.washington.edu/problem/search?keyword=tree+traversals

Problem 5 in allen Übungstests enthält auch diese Problemtypen.

Versuchen Sie in der Abschlussprüfung, nur maximal ~5 Minuten pro Problem (also ~10 min insgesamt)mit `00% Genauigkeit zu verbringen.

Sammlungsrätsel

Ich konnte nur zwei Sammlungsrätsel mit Karten auf practice-it finden:

  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final8/collectionMystery
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final7/collectionMystery

Für dieses Thema schlage ich vor, dass du sicherstellst, dass du verstehst, wie genau sich die folgenden Datenstrukturen verhalten, wie effizient ihre verschiedenen Methoden sind und wie sie sich voneinander unterscheiden:

  • ArrayList
  • LinkedList
  • Stack
  • Queue
  • TreeSet
  • HashSet
  • TreeMap
  • HashMap

Polymorphismus-Rätsel

Hier finden Sie einige Übungsaufgaben: http://practiceit.cs.washington.edu/problem/search?keyword=polymorphism&Sprache=

Sie sollten sich für diese Aufgaben in der Abschlussprüfung Zeit nehmen, um sicherzugehen, dass Sie keinen dummen Fehler machen.

Wenn Sie an diesen Aufgaben arbeiten, stellen Sie sicher, dass Sie ein solides konzeptionelles Verständnis von dem haben, worum es geht. Der Spickzettel, den wir im Abschnitt ausgeteilt haben, sollte sehr nützlich sein.

Programmierprobleme

Für die Fragen zu Binärbäumen und verknüpften Listen habe ich die Fragen grob nach Schwierigkeitsgrad sortiert.

Ich empfehle Ihnen dringend, zuerst die mittelschweren bis schweren Fragen zu lösen und nur dann die leichten bis schweren Fragen zu versuchen, wenn Sie Schwierigkeiten mit den schwereren haben.

Haftungsausschluss: Ich habe den Schwierigkeitsgrad sozusagen mit dem Auge beurteilt. Es kann sein, dass ich Nuancen bei bestimmten Fragen übersehen habe, die sie einfacher oder schwieriger machen, als ich ursprünglich dachte.

Vergleichbare Programmierung

Dieses Problem erfordert, dass Sie die gesamte Klasse implementieren: http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final8/Office

Bei den folgenden Aufgaben müssen Sie nur die Methode compareTo implementieren. Ich würde empfehlen, trotzdem zu versuchen, die komplette Klasse zu schreiben, da dies wahrscheinlich in der Abschlussprüfung verlangt wird.

Anmerkung: practice-it hat einige weitere Aufgaben zu diesem Thema, aber ich habe diejenigen ausgewählt, die etwas komplexer aussehen. Einige Comparable-Probleme auf practice-it verlangen, dass man eine Klasse zusätzlich zur Implementierung von Comparable erweitert – das wird in der Abschlussprüfung dieses Quartals nicht verlangt.

  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/midterms/midterm1/BankAccount
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/midterms/midterm3/Food
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/midterms/midterm4/MovieRating
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/midterms/midterm5/Pokemon
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/comparable/Location
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/midterms/midterm2/Rational

Binary Tree Programming (traversal)

Hinweis: Die Praxisprüfung hat mehr Probleme, aber ich habe einige ausgewählt, die gut aussahen/knifflig schienen. Die Praxisprüfungen haben auch einige gute Fragen, obwohl es einige Überschneidungen mit der Praxis-it geben wird. Wie oben erwähnt, arbeiten Sie vorrangig an den schwierigeren Fragen.

Leicht bis mittel:

  • http://practiceit.cs.washington.edu/problem/view/bjp3/chapter17/e18%2DinOrderList
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/countLeaves
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/height
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/isFull
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/printLevel

Mittel bis schwer:

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/depthSum
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/numEmpty
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/printLeaves
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/evenBranches
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final2/countMultiples
  • http://practiceit.cs.washington.edu/problem/view/bjp4/chapter17/e9%2Dequals

Binäre Baumprogrammierung (Modifikation)

Gleich wie oben – Übung – es hat mehr Probleme, Ich habe interessante ausgewählt, Übungsprüfungen haben gute Fragen mit einigen Überschneidungen, priorisieren Sie die Arbeit an anspruchsvollen Problemen.

Für dieses Thema ist es absolut wichtig, dass Sie dasx = change(x) Muster gut verstehen. Der Styleguide enthält einige Hinweise zu x = change(x) (vor allem eine Auflistung von Dingen, die man nicht tun sollte/einige Beispiele), die hilfreich sein könnten.

Haftungsausschluss: die Unterscheidung zwischen „mittelschweren“ und „schweren“ Fragen ist hier für mich irgendwie verschwommen, daher weiß ich nicht, ob sie wirklich richtig sortiert sind.

Leicht bis mittelschwer:

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/removeLeaves
  • http://practiceit.cs.washington.edu/problem/view/bjp4/chapter17/e20%2DmakePerfect
    • Dieses Problem gibt dir eine „Höhe“-Methode. Du solltest versuchen, die Methode „height“ hier selbst zu schreiben: http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/height
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final5/flip
  • http://practiceit.cs.washington.edu/problem/view/bjp4/chapter17/e17%2DcombineWith
  • http://practiceit.cs.washington.edu/problem/view/bjp3/chapter17/e19%2DevenLevels

Mittel bis schwer:

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/tighten
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/completeToLevel
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/construct
  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/limitPathSum
  • http://practiceit.cs.washington.edu/problem/view/bjp4/chapter17/e15%2Dtrim
  • http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final6/removeMatchingLeaves

Verknüpfte Listenprogrammierung

Gleiches wie oben.

Wenn Sie bei der Arbeit an einem Problem mit einer verketteten Liste jemals denken: „Mensch, ich wünschte, ich könnte einen Hilfsstapel verwenden“, ist das oft ein Hinweis darauf, dass das Problem mit der verketteten Liste einfacher wäre, wenn Sie versuchen würden, es rekursiv zu lösen.

Wenn man ein Problem rekursiv löst, kann man Variablen und Informationen auf jeder Ebene/jedem Stackframe „speichern“ – so erhält man im Grunde einen impliziten Hilfsstack.

Ein (impliziter) Stack ist jedoch nicht unbedingt für alle Probleme mit verknüpften Listen nützlich, also versuchen Sie nicht, die Rekursion an Stellen zu erzwingen, an denen sie nicht natürlich erscheint.

Allerdings sollten Sie bedenken, dass Sie Code mit Schleifen durch Code mit Rekursion ersetzen können und umgekehrt, wenn Sie sich genug Mühe geben. (Die Frage ist, ob es tatsächlich eine gute Idee ist, das zu tun…)

Einfach bis mittelschwer:

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/min

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/lastIndexOf

    Versuchen Sie, dies rekursiv zu tun!

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/countDuplicates

    Ausnutzen, wie die Liste sortiert ist

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/transferFrom

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/equals

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/doubleList

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/switchPairs

Mittel bis schwer:

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/split

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/removeRange

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/reverse

    Versuchen Sie dies sowohl rekursiv als auch iterativ zu tun!

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/takeSmallerFrom

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/removeAll

Leave a Reply