Articles / 4 září, 2021

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

Jak se učit

Programování je do značné míry o řešení aplikovaných problémů, nikoli o memorování.To znamená, že nejlepší způsob, jak se připravit na zkoušky z programování, není sedět a číst si slajdy – ale řešit spoustu problémů.

V důsledku toho vám důrazně doporučuji, abyste při přípravě postupovali následovně:

Zkuste od nynějška řešit minimálně 3 až 4 programátorské problémy denně.

Do zkoušky zbývá přibližně 12 dní. Pokud budete řešit 4 problémy denně, budete mít do zkoušky vyřešeno asi 30-50 problémů, což vám dá OBROVSKOU výhodu oproti lidem, kteří se učí na poslední chvíli. Pokud máte velmi nabitý program, snažte se řešit alespoň 1 problém denně.

Je to částečně proto, že budete mít mnohem více zkušeností s řešením problémů než lidé, kteří se šprtají na poslední chvíli, a částečně proto, že někdy prostě opakovaně používáme problémy na cvičení-na závěrečnou zkoušku. Pokud máte za sebou 30-50 vyřešených problémů, je pravděpodobnost, že u zkoušky narazíte na nějakou chybu, mnohem vyšší…

Takto budete mít také čas klást otázky, pokud narazíte na problémy, které vás zarazí.

Zkuste si v kalendáři naplánovat každý den hodinový blok, kdy si plánujete jen sednout a pracovat na problémech. (Také se ujistěte, že jste začali pracovat na HW 8 dříve, abyste měli dostatek času jak na studium, tak na HW).
Vyhraďte si den, kdy si sednete a budete řešit několik problémů ze záhadného tématu.

Měli byste se snažit procvičovat do té míry, abyste záhadné problémy zvládli spolehlivě a se 100% přesností. Možná bude produktivnější sednout si jeden den a vypracovat několik úloh najednou, abyste se mohli procvičit. (Například tento víkend možná zkuste udělat hromadu úloh opolymorfismu)
Zkuste vyřešit cvičné úlohy najednou. Ne „upravovat a překompilovávat“.

V závěrečném testu nebudete mít k dispozici překladač, který by vaši práci zkontroloval. Snažte se vyřešit problémyna první pokus. Než stisknete tlačítko „odeslat“, použijte tužku a papír, abyste si problémy zdůvodnili.

Pokud se vám nedaří spolehlivě vyřešit cvičné úlohy správně na první pokus, znamená to, že potřebujete mnohem více procvičovat.

(To znamená, že pro začátek se soustřeďte hlavně na to, abyste problémy vyřešili správně.

Jakmile se s tématem relativně dobře seznámíte, dejte přednost tomu, abyste problémy vyřešili správně na první pokus.)
Udržujte si průběžný seznam „věcí, ve kterých se musíte zlepšit“.

Když uděláte chybu, něco přehlédnete nebo si všimnete, že jste zmatení, zapište si to. průběžný seznam chyb vám pomůže řídit se tím, s jakými typy problémů máte potíže a co byste měli více studovat.

Můžete například zjistit, že někdy máte problémy typu practice-it špatně, protože jste zapomněli přidat kontrolu výjimky. To by mohlo naznačovat, že v závěrečné zkoušce byste si měli dávat větší pozor na čtení instrukcí.

Nebo můžete zjistit, že máte potíže s úlohami se spojovými seznamy, kde musíte zpracovat dva spojové seznamy. To by mohlo být dobré, kdybyste požádali o pomoc technického asistenta.
Produktivní boj je dobrý, neproduktivní boj je špatný.

Je normální, že se při řešení problémů trápíte. Snažte se však vést „produktivní“ boj, nikoliv „neproduktivní“ boj. Pokud pracujete na problému a máte pocit, že děláte stálý pokrok (i když je pomalý), pak je to „produktivní“ boj.

Jestliže jste se však zasekli a uchýlili jste se k náhodným změnám, abyste zjistili, zda fungují, je to „neproduktivní“ boj. Pokud se dostanete do „neproduktivního“ stádia, pak byste měli problém odložit, dát si pauzu, zkusit pracovat na jiném problému, zkusit někoho požádat o pomoc atd…

Problémy s kolekcemi

Problémy s procházením a vkládáním binárních stromů

Několik cvičných problémů najdete zde: http://practiceit.cs.washington.edu/problem/search?keyword=tree+traversals

Problém 5 na všech cvičných zkouškách obsahuje také tyto typy problémů.

Na závěrečné zkoušce se snažte strávit nad každým z těchto problémů maximálně ~5 minut (tedy ~10 min celkem)s `00% přesností.

Záhada kolekcí

Na practice-it se mi podařilo najít pouze dvě úlohy záhady kolekcí zahrnující mapy:

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

Pro toto téma doporučuji, abyste se ujistili, že chápete, jak přesně se chovají následující datové struktury, jak efektivní jsou jejich různé metody a jak se od sebe liší:

ArrayList
LinkedList
Stack
Queue
TreeSet
HashSet

TreeMap
HashMap

Záhada polymorfismu

Několik cvičných úloh najdete zde: http://practiceit.cs.washington.edu/problem/search?keyword=polymorphism&jazyk=

Při řešení těchto úloh v závěrečném testu byste si měli dát na čas, abyste se ujistili, že neuděláte hloupou chybu.

Při práci na těchto úlohách se ujistěte, že máte pevnou koncepční představu o tom, o co jde. Velmi užitečný by vám měl být cheatsheet, který jsme rozdali na sekci.

Programovací problémy

U otázek týkajících se binárních stromů a propojených seznamů jsem otázky seřadil zhruba podle obtížnosti.Důrazně doporučuji, abyste nejprve upřednostnili řešení středně těžkých až těžkých otázek, a teprve pokud budete mít potíže s těmi těžšími, zkuste lehké až těžké otázky.

Odmítnutí odpovědnosti: Obtížnost jsem posuzoval tak, že jsem se na problémy podíval od oka. Je možné, že jsem přehlédl některé otázky, které je činí lehčími nebo těžšími, než jsem si původně myslel.

Srovnatelné programování

Tato úloha vyžaduje, abyste implementovali celou třídu: http://practiceit.cs.washington.edu/problem/view/cs2/exams/finals/final8/Office

Následující úlohy vyžadují, abyste implementovali pouze metodu compareTo. Doporučoval bych, abyste se i tak pokusili napsat celou třídu, protože to po vás pravděpodobně budou chtít v závěrečném testu.

Poznámka: cvičení – je tam několik dalších úloh na toto téma, ale ručně jsem vybral ty, které vypadaly trochu složitěji. Některé úlohy o Comparable na practice-it po vás chtějí, abyste kromě implementace Comparable rozšířili třídu – to se po vás v závěrečném testu v tomto čtvrtletí nebude chtít.

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

Programování binárních stromů (traverzování)

Poznámka: praxe – má více problémů, ale ručně jsem vybral některé, které vypadaly dobře/zdály se mi záludné. Cvičné finále má také několik dobrých otázek, i když se budou trochu překrývat s cvičným-it. Jak je uvedeno výše, upřednostněte práci na těch těžších.

Lehké až střední:

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

Střední až těžké:

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

Programování binárních stromů (modifikace)

Stejné jako výše — praxe- má více problémů, Vybral jsem zajímavé, cvičné maturity majídobré otázky s určitým přesahem, upřednostnit práci na náročných problémech.

Pro toto téma je naprosto nezbytné, abyste dobře rozuměli vzorux = change(x). Průvodce stylem zde má několik poznámek o x = change(x)(většinou vyjmenovává spoustu věcí, které byste neměli dělat / má několik příkladů), které by mohly být užitečné.

Odmítnutí odpovědnosti: Rozdíl mezi „středně těžkými“ a „těžkými“ otázkami se mi tu nějak rozmazal,takže nevím, jestli jsou opravdu správně seřazeny.

Snadné až střední:

http://practiceit.cs.washington.edu/problem/view/cs2/sections/binarytrees/removeLeaves
http://practiceit.cs.washington.edu/problem/view/bjp4/chapter17/e20%2DmakePerfect
- Tato úloha vám dává metodu „výška“. Zde byste měli zkusit napsat metodu „výška“ sami: 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

Střední až těžká:

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

Programování propojených seznamů

Stejné jako výše.

Jestliže se někdy přistihnete, že si při prácina problému spojového seznamu říkáte „Jé, kéž bych mohl použít pomocný zásobník“, je to často indikátor toho, že problém spojového seznamu bude jednodušší, pokud se ho pokusíte vyřešit rekurzivně.

Při rekurzivním řešení problému můžete „ukládat“ proměnné a informace na každou úroveň/na každý rámec zásobníku – tím v podstatě získáte implicitní pomocný zásobník.

Mít (implicitní) zásobník však nemusí být nutně užitečné pro všechny problémy spojového seznamu, takže se nesnažte vnucovat rekurzi tam, kde se nezdá přirozená.

Přesto mějte na paměti, že při dostatečném úsilí můžete nahradit kód používající smyčky kódem používajícím rekurzi a naopak. (Otázkou je, zda je to skutečně dobrý nápad…)

Snadno až středně:

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

Zkuste to udělat rekurzivně!
http://practiceit.cs.washington.edu/problem/view/cs2/sections/linkedlists/countDuplicates

Ujistěte se, že využíváte způsobu řazení seznamu
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