Articles /

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

Come studiare

La programmazione, in larga misura, riguarda la risoluzione di problemi applicati, e non la memorizzazione.

Come risultato, vi raccomando fortemente di fare quanto segue quando vi preparate:

  1. Provate a lavorare su un minimo di 3 o 4 problemi di programmazione al giorno, iniziando ora.

    Ci sono circa 12 giorni all’esame. Se fai 4 problemi al giorno, avrai risolto circa 30-50 problemi per l’esame, il che ti darà un vantaggio GIGANTISSIMO sulle persone che studiano all’ultimo minuto. Se avete un programma molto occupato, provate almeno a fare 1 problema al giorno.

    Questo è in parte perché avrete molta più esperienza nel risolvere i problemi rispetto alle persone che studiano all’ultimo minuto, e in parte perché a volte riutilizziamo i problemi in pratica per l’esame finale. Se avete 30-50 problemi risolti sotto la cintura, le probabilità di incontrare un errore all’esame sono molto più alte…

    In questo modo, avrete anche il tempo di fare domande se vi imbattete in problemi che vi bloccano.

    Provare a programmare un blocco di 1 ora ogni giorno sul vostro calendario dove pensate di sedervi e lavorare sui problemi. (Assicurati anche di iniziare presto il HW 8, per assicurarti di avere tempo a sufficienza sia per studiare che per fare il tuo HW).

  2. Assegnati un giorno in cui ti siedi e lavori su un mucchio di problemi di un argomento misterioso.

    Dovresti provare e fare pratica fino al punto in cui puoi completare i problemi misteriosi in modo affidabile e con una precisione del 100%. Potrebbe essere più produttivo sedersi un giorno e lavorare su un mucchio di problemi in una volta sola, in modo da poter fare pratica. (Per esempio, questo fine settimana, magari prova a fare un mucchio di problemi di polimorfismo)

  3. Prova a risolvere i problemi di pratica in un colpo solo. Non “editare e ricompilare”.

    In finale, non avrete un compilatore per controllare il vostro lavoro. Fate del vostro meglio per risolvere i problemi al primo tentativo. Usate carta e penna per ragionare sui problemi prima di premere il pulsante “submit”.

    Se non riuscite a risolvere in modo affidabile i problemi di pratica al primo tentativo, significa che avete bisogno di molta più pratica.

    (Detto questo, per cominciare, concentratevi principalmente sul risolvere i problemi al primo tentativo.Una volta che siete relativamente a vostro agio con un argomento, date priorità al risolvere i problemi al primo tentativo).

  4. Mantenete una lista di “cose che dovete migliorare”.

    Quando fate un errore, trascurate qualcosa, o notate che siete confusi, scrivetelo.Usate la vostra lista di errori per aiutarvi a capire quali tipi di problemi avete problemi e quali dovete studiare di più.

    Per esempio, potreste scoprire che a volte sbagliate i problemi di pratica perché vi dimenticate di aggiungere un controllo di eccezione. Questo potrebbe indicare che nell’esame finale dovreste stare più attenti a leggere le istruzioni.

    Oppure, potreste scoprire di avere difficoltà con problemi di liste collegate in cui dovete lavorare su due liste collegate. Questa potrebbe essere una buona cosa per cui chiedere aiuto all’assistente.

  5. La lotta produttiva è buona; la lotta improduttiva è cattiva.

    E’ normale essere in difficoltà quando si lavora sui problemi. Tuttavia, cerca di avere una lotta “produttiva”, non una lotta “improduttiva”. Se stai lavorando su un problema e senti che stai facendo progressi costanti (anche se sono lenti), allora questa è una lotta “produttiva”.

    Se invece sei bloccato e hai fatto ricorso a cambiamenti casuali per vedere se funzionano, questa è una lotta “improduttiva”. Se arrivi allo stadio “improduttivo”, allora dovresti mettere da parte il problema, fare una pausa, provare a lavorare su un altro problema, provare a chiedere aiuto a qualcuno, ecc…

Problemi di raccolta

Problemi di attraversamento e inserimento di alberi binari

Puoi trovare alcuni problemi di pratica qui: http://practiceit.cs.washington.edu/problem/search?keyword=tree+traversals

Il problema 5 su tutti gli esami pratici ha anche questi tipi di problemi.

Sul finale, prova a spendere solo un massimo di ~5 minuti ciascuno su questi problemi (quindi ~10 min in totale) con una precisione del 100%.

Collezioni misteriose

Sono riuscito a trovare solo due problemi di collezioni misteriose che coinvolgono mappe su practice-it:

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

Per questo argomento, ti suggerisco di assicurarti di capire come si comportano esattamente le seguenti strutture dati, quanto sono efficienti i loro vari metodi e come differiscono l’una dall’altra:

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

Mistero del polimorfismo

Puoi trovare alcuni problemi di pratica qui: http://practiceit.cs.washington.edu/problem/search?keyword=polymorphism&language=

Dovresti prenderti il tuo tempo su questi problemi nel finale per essere sicuro di non fare uno stupido errore.

Quando lavori su questi problemi, assicurati di avere una solida comprensione concettuale di quello che sta succedendo. Il cheatsheet che abbiamo distribuito in sezione dovrebbe essere molto utile.

Problemi di programmazione

Per le domande dell’albero binario e della lista collegata, ho ordinato le domande approssimativamente per difficoltà.Vi raccomanderei fortemente di dare priorità alla risoluzione delle domande medio-dure prima, e provare solo le domande facili-dure se avete difficoltà con quelle più difficili.

Disclaimer: Ho valutato la difficoltà con una sorta di occhio-ballando i problemi. Potrei aver tralasciato delle sfumature a certe domande che le rendono più facili o più difficili di quanto pensassi inizialmente.

Programmazione comparabile

Questo problema richiede di implementare l’intera classe: http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final8/Office

I problemi seguenti richiedono di implementare solo il metodo compareTo. Raccomando comunque di provare a scrivere la classe completa, dato che è quello che probabilmente vi verrà chiesto di fare nel finale.

Nota: practice-it ha alcuni altri problemi su questo argomento, ma ne ho scelti alcuni che sembravano un po’ più complessi. Alcuni problemi di Comparable su practice-it ti chiedono di estendere una classe oltre ad implementare Comparable — non ti sarà richiesto di farlo nell’esame finale di questo trimestre.

  • 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

Programmazione ad albero binario (traversale)

Nota: La pratica ha un maggior numero di problemi, ma ne ho scelti alcuni che sembravano buoni/sembravano complicati. La pratica finale ha anche alcune buone domande, anche se ci sarà qualche sovrapposizione con la pratica-it. Come detto sopra, date la priorità al lavoro su quelle più difficili.

Facile a medio:

  • 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

Medio a difficile:

  • 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

Programmazione ad albero binario (modifica)

Come sopra — la pratica ha più problemi, Ne ho scelti di interessanti, gli esami finali di pratica hanno buone domande con alcune sovrapposizioni, dare priorità al lavoro su problemi impegnativi.

Per questo argomento, è assolutamente essenziale che tu abbia una buona comprensione del modello x = change(x). La guida di stile ha alcune note su x = change(x) qui (per lo più, elenca un mucchio di cose che non si dovrebbero fare/ha alcuni esempi) che potrebbero essere utili.

Disclaimer: la distinzione tra domande “medie” e “difficili” è un po’ sfocata per me, quindi non so se sono davvero ordinate correttamente.

Facile a medio:

  • http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/removeLeaves
  • http://practiceit.cs.washington.edu/problem/view/bjp4/chapter17/e20%2DmakePerfect
    • Questo problema ti dà un metodo “altezza”. Dovresti provare a scrivere il metodo “altezza” qui: 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

Medium to hard:

  • 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

Programmazione di liste collegate

Come sopra.

Inoltre, se vi trovate a pensare “Cavolo, vorrei poter usare uno stack ausiliario” quando lavorate su un problema di lista collegata, questo è spesso un indicatore che il problema della lista collegata sarà più facile se provate a risolverlo ricorsivamente.

Quando si risolve un problema in modo ricorsivo, si possono “immagazzinare” variabili e informazioni su ogni livello/su ogni frame dello stack — questo fondamentalmente dà uno stack ausiliario implicito.

Avere uno stack (implicito) non sarà necessariamente utile per tutti i problemi di liste collegate, quindi non cercate di forzare la ricorsione in posti dove non sembra naturale.

Detto questo, tenete a mente che potete sostituire il codice che usa i loop con quello che usa la ricorsione, e viceversa, con sufficiente sforzo. (La domanda è: è davvero una buona idea farlo…)

Facile a medio:

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

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

    Prova a fare questo ricorsivamente!

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

    Assicurati di sfruttare come la lista è ordinata

  • 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

Medio a difficile:

  • 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

    Prova a farlo sia ricorsivamente che iterativamente!

  • 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