ROB BOWDEN: Hej, jag är Rob Bowden, och låt oss tala om quiz0. Så första frågan. Detta är den fråga där du behövs för att koda numret 127 i de binära glödlampor. Om du ville, du kunde gör den vanliga konvertering från bi-- eller från decimal till binär. Men det är förmodligen kommer att ta en hel del tid. Jag menar, du kan räkna ut det, OK, 1 är det, 2 är där, 4 är där, är där 8. Enklare sätt är 127 128 minus ett. Den längst till vänster glödlampa är den 128-bit. Så 127 är egentligen bara alla andra glödlampor, eftersom det är längst till vänster glödlampa minus ett. Det var allt för denna fråga. 

Fråga ett. Så med 3 bitar som du kan representerar 8 olika värden. Varför är då 7 den största icke-negativ decimalt heltal du kan representera? Tja, om vi bara kan representerar 8 olika värden, vad vi ska bli representerar är 0 till 7. 0 tar upp ett av värdena. 

Fråga två. Med n bitar, hur många distinkta värden kan du representerar? Så, med n bitar, har du 2 möjliga värden för varje bit. Så vi har två möjliga värden för den första biten, två möjliga värden för det andra, två möjligt för den tredje. Och så det finns 2 gånger 2 gånger 2, och slutligen svaret är 2 till n. 

Fråga tre. Vad finns 0x50 i binär? Så kom ihåg att hexadecimal har en mycket enkel konvertering till binär. Så här behöver vi bara titta på den 5 och 0 oberoende av varandra. Så vad är 5 i binär? 0101, det är 1 bit och 4 bit. Vad är 0 i binär? Inte knepigt. 0000. Så bara sätta ihop dem, och som är fulla antalet i binär. 01.010.000. Och om du ville du kunde ta av det längst till vänster noll. Det är irrelevant. 

Så då alternativt vad som är 0x50 i decimal? Om du ville, could-- dig om du är mer bekväm med det binära, du kan ta det binära svar och omvandla det till decimal. Eller vi kan bara minnas som hexadecimalt. Så att 0 är i 0-e plats, och den 5 är i det 16 till den första platsen. Så här har vi 5 gånger 16 till först, plus 0 gånger 16 till noll, är 80. Och om du tittat på Titeln på frågan, Det var CS 80, som var typ av en ledtråd till svaret på detta problem. 

Fråga fem. Vi har denna Scratch manus, vilket är upprepa 4 gånger jordnötssmör gelé. Så hur gör vi nu kod som i C? Tja, vi har här-- delen i fetstil är den enda del som du var tvungen att genomföra. Så vi har en 4 slinga som är kretsa 4 gånger, printf-ing jordnötssmör gelé, med ny linje som problemet frågar efter. 

Fråga sex, en annan Scratch problem. Vi ser att vi är i ett evigt loop. Vi säger variabeln i och sedan stega i med 1. Nu vill vi göra det i C. Det finns flera sätt som vi kunde ha gjort det här. Här råkade vi koda forever loop som ett tag (sant). Så vi deklarerar variabeln i, bara som vi hade variabeln i i Scratch. Deklarera variabeln i, och för evigt while (true), säger vi variabeln i. Så printf% Jag-- eller du kan har använt% d. Vi säger att variabeln, och sedan höja detta, i ++. 

Fråga sju. Nu vill vi göra något mycket liknande Mario dot c från problembild en. Vi vill skriva ut dessa hashtags, Vi vill skriva ut en fem med tre rektangel av dessa hashar. Så hur ska vi göra det? Nåväl, vi ger dig en hel gäng kod, och du bara måste fylla i tryck rutnät funktionen. 

Så vad gör PrintGrid ut? Jo du är förbi bredd och höjd. Så vi har ett yttre 4 loop, som är looping över alla rader i denna rutnät som vi vill skriva ut. Sedan har vi den inter kapslade 4 slinga, det är att skriva ut över varje kolumn. Så för varje rad, vi trycker på varje kolumn, en enda hash. Sedan i slutet av raden som vi skriver ut ett enda ny rad för att gå till nästa rad. Och det är det för hela nätet. 

Fråga åtta. En funktion som PrintGrid sägs har en sidoeffekt, men inte en återgång värde. Förklara skillnaden. Så detta är beroende av dig minnas vad en biverkning är. Tja, en återgång value-- vi vet PrintGrid inte har returvärde, eftersom här står det ogiltigt. Så allt som returnerar void egentligen inte tillbaka någonting. Så vad är det bieffekt? Tja, är en bieffekt något som slags kvarstår efter funktions slutar Det var inte bara tillbaka, och det var inte bara från ingångarna. 

Så, till exempel, vi kanske ändra en global variabel. Det skulle vara en bieffekt. I just detta fall, en mycket viktig sidoeffekt skriver ut på skärmen. Så det är en bieffekt att PrintGrid har. Vi trycker dessa saker på skärmen. Och du kan tänka dig att som en sidoeffekt, eftersom det är något som kvarstår efter den här funktionen avslutas. Det är något utanför av denna funktion som slutligen håller på att ändras, innehållet på skärmen. 

Fråga nio. Betrakta programmet nedan, till vilket radnummer har lagts till för diskussionens skull. Så i det här programmet är vi bara ringer getString, lagra det i denna variabel s, och sedan skriver ut variabeln s. OK. Så förklara varför linje man är närvarande. #include CS50 dot h. Varför behöver vi #include CS50 dot h? Jo vi kallar det GetString funktion, och getString definieras i CS50 biblioteket. Så om vi inte hade #include CS50 dot h, vi skulle få det implicit deklaration av getString funktionsfel från kompilatorn. Så vi måste inkludera library-- Vi måste inkludera header-filen, annars kompilatorn kommer inte inse att getString existerar. 

Förklara varför linje två är närvarande. Så standard io dot h. Det är exakt samma som det föregående problemet, utom i stället för att hantera GetString, vi pratar om printf. Så om vi inte säga att vi behöver att inkludera standard io dot h, då skulle vi inte kunna att använda printf funktion, eftersom kompilatorn skulle inte veta om det. 

Why-- vilken betydelse av ogiltig i linje fyra? Så här har vi int main (void). Det är bara att säga att vi blir inte kommandoraden argument till main. Kom ihåg att vi kunde säga int huvud int argc sträng argv parentes. Så här säger vi bara tomrum att säga att vi ignorerar kommandoradsargument. 

Förklara, med avseende på minne, exakt vad getString i linje sex returer. GetString återvänder ett block av minne, en array av tecken. Det är verkligen returnera en pekare till det första tecknet. Tänk på att en sträng är en röding stjärna. Så ar är en pekare till den första tecken oavsett i vilken strängen är att användaren anger på tangentbordet. Och att minnet råkar vara malloced, så att minnet är i högen. 

Fråga 13. Betrakta programmet nedan. Så allt det här programmet gör är printf-ing 1 dividerat med 10. Så när de sammanställs och avrättades, det här programmet utgångar 0.0, även om 1 dividerat med 10 är 0,1. Så varför är det 0,0? Nåväl, detta är därför att av heltalsdivision. Så en är ett heltal, 10 är ett heltal. Så 1 dividerat med 10, allt behandlas som heltal, och i C, när vi gör heltalsdivision, Vi trunkera något decimalkomma. Så 1 dividerat med 10 0, och då vi försöker för att skriva ut det som ett flyttal, så noll ut som en flottör är 0,0. Och det är därför vi får 0.0. 

Betrakta programmet nedan. Nu är vi skriver ut 0,1. Så ingen heltalsdivision, vi bara skriva ut 0.1, men vi skriver ut det till 28 decimaler. Och vi får denna 0.1000, ett helt gäng av nollor, 5 5 5, bla bla bla. Så frågan här är varför gör det skriva att, i stället för att exakt 0,1? 

Så anledningen här är nu flyttal vaghet. Tänk på att en flottör är bara 32 bitar. Så vi kan bara representera ett begränsat antal av flyttalsvärden med dem 32 bitar. Jo det finns slutligen oändligt många flyttalsvärden, och det finns oändligt många flytande punkt värden i mellan 0 och 1, och vi är självklart kunna representerar ännu fler värden än så. Så vi måste göra uppoffringar för att kunna representera de flesta värden. 

Så ett värde som 0,1, tydligen Vi kan inte representera det exakt. Så istället för att representera 0,1 vi gör bästa vi kan representera denna 0.100000 5 5 5. Och det är ganska nära, men för många tillämpningar du behöver oroa dig flyttal vaghet, eftersom vi bara inte kan representera alla flytande punkter exakt. 

Fråga 15. Tänk koden nedan. Vi är bara att skriva ut 1 plus 1. Så det finns ingen konst här. 1 plus 1 beräknas till 2, och då vi skriver ut det. Detta skriver bara 2. 

Fråga 16. Nu ska vi skriva ut tecknet 1 plus tecknet 1. Så varför gör detta inte skriva ut samma sak? Tja tecknet 1 plus tecknet 1, karaktären 1 har ASCII-värdet 49. Så det här är verkligen säger 49 plus 49, och i slutändan kommer detta att skriva ut 98. Så det här inte ut 2. 

Fråga 17. Slutföra genomförandet av udda nedan på ett sådant sätt att funktionen returnerar true om n är udda och falskt om n är jämnt. Detta är en stor ändamål för mod operatör. Så vi tar våra argument n, om n mod 2 är lika med 1, väl det betyder att n uppdelat av 2 hade en rest. Om n divideras med 2 hade en rest, som betyder att n är udda, så vi return true. Else återvänder vi falskt. Du kunde också ha gjort n mod 2 jämlikar noll, returnera false, annars return true. 

Betrakta den rekursiva funktionen nedan. Så om n är mindre än eller lika med 1, avkastning 1, annars retur n gånger f n minus ett. Så vad är denna funktion? Nåväl, detta är bara fakulteten. Detta är fint representerad såsom n faktoriell. 

Så fråga 19 nu, vill vi ta detta rekursiv funktion. Vi vill göra det iterativ. Så hur gör vi det? Väl för personalen lösning, och återigen finns det flera sätt som du skulle ha gjort att börjar vi med denna int produkt är lika med ett. Och genom hela denna för loop, vi kommer att multiplicera produkt att slutligen sluta med fullständig faktor. Så för int jag är lika med 2, är i mindre än eller lika med n, i ++. 

Du kanske undrar varför jag är lika med 2. Tja, kom ihåg att vi här har att se till att vårt grundscenario är korrekt. Så om n är mindre än eller lika till 1, vi bara åter 1. Så här borta, börjar vi på jag är lika med 2. Tja, om jag var 1, då the-- eller om n var 1, sedan för loop skulle inte köra alls. Och så skulle vi bara retur produkt som är ett. Likaså om n var något mindre än 1-- om det var 0, -1, whatever-- vi skulle ändå att återvända 1, vilket är precis vad rekursiva versionen gör. 

Nu, om n är större än 1, då ska vi att göra åtminstone en variant av denna slinga. Så låt oss säga n är 5, då är vi kommer att göra produkttider är lika med 2. Så nu produkt är 2. Nu ska vi göra produkttider är lika med 3. Nu är det 6. Produkttider är lika med 4, nu är det 24. Produkttider lika med 5, nu är det 120. Så sedan slutligen, vi återvänder 120, vilket är korrekt 5 faktoriell. 

Fråga 20. Detta är en där du måste fylla i denna tabell med en given algoritm, något som vi har sett, att passar dessa algoritmiska körningen gånger dessa asymptotiska körtider. Så vad är en algoritm som är omega på 1, men stort o n? Så det skulle vara oändligt många svar här. Det som vi har sett nog mest ofta är bara linjär sökning. 

Så i bästa fall scenario, objektet är vi söker är på början av listan och så på omega 1 steg, det första vi kontrollerar, vi bara omedelbart återvända att vi hittat objektet. I det värsta scenariot, objektet är i slutet, eller objektet inte finns i listan alls. Så vi måste söka hela listan, alla n element, och det är därför det är o n. 

Så nu är det något som är både omega n log n, och stora O n log n. Jo den mest relevanta sak vi har sett här är Merge sort. Så sammanfoga sortera, kom ihåg, är ytterst teta av n log n, där theta är definierad om både omega och stora O är desamma. Både n log n. 

Vad är något som är omega N, och O i n kvadrat? Tja, återigen finns det flera möjliga svar. Här råkar vi säga bubbla slag. Insättningssortering skulle också fungera här. Tänk på att bubbla sortera har att optimering där, Om du har möjlighet att få igenom hela listan utan att behöva göra några swappar, då, ja, vi omedelbart kan återgå till att listan sorterades till att börja med. Så i bästa fall, det är bara omega n. Om det är inte bara ett fint sorterade listan till att börja med, då har vi O n kvadrat swappar. Och slutligen har vi val Sortera för n kvadrat, både omega och stora O. 

Fråga 21. Vad är heltalsspill? Tja igen, likt tidigare, Vi har bara ändligt många bitar för att representera ett heltal, så kanske 32 bitar. Låt oss säga att vi har ett heltal. Sedan slutligen den högsta positivt tal vi kan representera är 2 till 31 minus ett. Så vad händer om vi försöker då inkrementera som heltal? Nåväl, vi kommer att gå från 2 till 31 minus 1, ända ner till minus 2 till 31. Så här heltalsspill är när du håller uppräkning, och i slutändan kan du inte bli högre och det bara sveper hela vägen tillbaka runt till ett negativt värde. 

Vad sägs om en buffer overflow? Så en buffert overflow-- ihåg vad en buffert är. Det är bara en bit av minnet. Någonting liknande en array är en buffert. Så en buffer overflow är när du försöker komma åt minnet längre än till slutet av den arrayen. Så om du har en matris med storlek 5 och du försöker komma åt array fäste 5 eller konsol 6 eller bygel 7, eller något bortom slutet, eller ens något below-- array bygel negativ 1-- alla dessa är buffertspill. Du vidrör minne på dåliga sätt. 

Fråga 23. Så i den här behöver du att genomföra strlen. Och vi berätta att du kan antar s kommer inte vara null, så du inte behöver göra någon kontroll för null. Och det finns flera sätt du kunde ha gjort det här. Här har vi bara ta det enkelt. Vi börjar med en räknare, n. n är att räkna hur många tecken som finns. Så vi börjar på 0, och då är vi iterera över hela listan. 

S är bygel 0 lika med den null terminator karaktär? Kom ihåg att vi är ute efter null terminator tecken att avgöra hur länge vår sträng är. Det kommer att upphöra varje relevant sträng. Så är s fäste 0 lika till noll terminator? Om det inte är, då vi kommer att titta på s konsol 1, s konsol 2. Vi håller på tills vi hitta null terminator. När vi har hittat den, då n innehåller den totala längden på strängen, och vi kan bara tillbaka det. 

Fråga 24. Så det här är den där du måste göra avvägning. Så en sak är bra i en sätt, men på vilket sätt är det dåligt? Så här, Merge sort tenderar att vara snabbare än bubbla slag. Med detta sagt that-- väl, det är flera svar här. Men det viktigaste är att bubbla sortera är omega n för en sorterad lista. 

Kom ihåg att bordet såg vi bara tidigare. Så bubbla sorterar omega av n, det bästa scenariot är det ska kunna gå över listan en gång, fastställa Hej det här är redan sorteras och retur. Merge sort, oavsett vad du gör, är omega n log n. Så för sorterad lista, bubbla sortera kommer att bli snabbare. 

Nu vad om länkade listor? Så en länkad lista kan växa och krympa för att passa så många element som behövs. Efter att ha sagt that-- så vanligtvis direkt jämförelse kommer att bli en länkad lista med en array. Så även om arrayer kan lätt växa och krympa för att passa så många element efter behov, lista en länkad jämfört med en array-- en arrayen har slumpvis åtkomst. Vi kan indexera i någon särskilt element i arrayen. 

Så för en länkad lista, kan vi inte bara att gå till det femte elementet, vi har att passera från början tills vi kommer till det femte elementet. Och det kommer att hindra oss från gör något som binär sökning. På tal om binär sökning, binär sökning tenderar att vara snabbare än linjär sökning. Efter att ha sagt that-- så, en möjlig sak är att du inte kan göra binär Sök på länkade listor, Du kan bara göra det på matriser. Men förmodligen ännu viktigare, du kan inte göra binär sökning på en samling som inte sorteras. Upfront kan du behöva sortera arrayen, och endast då kan du gör binär sökning. Så om din sak är inte sorterade till att börja med, då linjär sökning kan också gå fortare. 

Fråga 27. Så anser programmet nedan, som kommer att vara i nästa bild. Och det är det där vi är kommer att vilja att uttryckligen ange värden för olika variabler. Så låt oss titta på det. 

Så linje ett. Vi har int x är lika med 1. Det är det enda som har hänt. Så vid linje ett, ser vi i vår bord, att y, a, b, och TMP är alla blackout. Så vad är x? Jo vi bara satt det lika med 1. Och sedan linje två, ja, ser vi att y är satt till 2, och tabellen är redan fyllas i för oss. Så x är 1 och y är 2. 

Nu, linje tre, är vi nu inuti växlingsfunktionen. Vad gjorde vi passerar byta? Vi passerade et-tecken x för a, och et-y för miljarder. Där problemet tidigare angav att adressen för x är 0x10, och adressen till y är 0x14. Så a och b är lika med 0x10 och 0x14, respektive. 

Nu på rad tre, vad är x och y? Tja, har ingenting förändrats om x och y vid denna punkt. Även om de är i en huvud stack ram, de fortfarande har samma värden som de gjorde innan. Vi har inte ändrat något minne. Så x är 1, y är 2. Okej. Så nu vi sa int tmp lika med stjärna en. Så vid linje fyra, allt är densamma med undantag för tmp. Vi har inte ändrat några värden för något, utom för tmp. Vi sätter tmp lika med stjärna en. Vad är stjärnan a? Tja, en poäng till x, så stjärnan en kommer att lika x, som är 1. Så allt kopieras ner, och TMP är satt till ett. 

Nu nästa rad. Stjärn a är lika stjärn miljarder. Så genom linje five-- bra igen, allt är samma förutom vad stjärn a är. Vad är stjärnan a? Jo, just sagt att vi stjärn a är x. Så vi ändra x till lika stjärnan f. Vad är stjärnan b? y. b pekar på y. Så stjärniga b är y. Så vi ställer x är lika med y, och allt annat är lika. Så vi ser i nästa rad att x är nu 2, och resten är bara kopieras ned. 

Nu i nästa rad, stjärna B lika tmp. Jo, just sagt att vi stjärn b är y, så vi ställer y lika med tmp. Allt annat är detsamma, så allt blir kopierat ner. Vi ställer y lika med tmp, vilket är en, och allt annat är lika. 

Nu äntligen, rad sju. Vi är tillbaka i huvudfunktionen. Vi är ute efter swap är klar. Vi har förlorat a, b, och tmp, men i slutändan vi inte ändra några värden av något på denna punkt, Vi kopierar bara x och y nedåt. Och vi ser att x och y är nu 2 och 1 i stället för 1 och 2. Den swap har framgångsrikt genomfört. 

Fråga 28. Antag att du stöter felmeddelandena nedan under kontorstid nästa år som en CA eller TF. Råd hur man rättar till vart och ett av dessa fel. Så odefinierad referens till getString. Varför kan ni se det här? Tja, om en elev använder GetString i sin kod, de har rätt hash inkluderat CS50 dot h att inkludera CS50 biblioteket. 

Tja, vad gör de måste fixa detta fel? De måste göra ett streck lcs50 på kommandoraden när de sammanställer. Så om de inte klarar klang streck lcs50, de är kommer inte att ha den verkliga kod som implementerar getString. 

Fråga 29. Underförstått att förklara biblioteksfunktion strlen. Ja detta nu, de har inte gjort korrekt hash inkludera. I detta särskilda fall var den header-fil de behöver för att inkludera är sträng dot h, och inkluderande sträng dot h, nu den student-- nu kompilatorn har tillgång till den förklaringar strlen, och den vet att din kod använder strlen fullständigt. 

Fråga 30. Fler procentuella omvandlingar än uppgifter argument. Så vad är det här? Väl ihåg att dessa procent signs-- hur de är relevanta för printf. Så i printf kan vi percent-- Vi kan skriva ut något som procent i backslash n. Eller vi kan skriva ut som procent i, utrymme, procent i, utrymme, procent i. Så för var och en av dem procenttecken, vi behöver att passera en variabel vid slutet av printf. 

Så om vi säger printf Paren procent I omvänt snedstreck n close Paren, ja, säger vi att vi är kommer att skriva ut ett heltal, men då vi inte klarar printf ett heltal att faktiskt skriva ut. Så här mer procent omvandlingar än uppgifter argument? Det är att säga att vi måste en hel massa procent, och vi har inte tillräckligt många variabler att faktiskt fylla i dessa procenttal. 

Och då definitivt, för fråga 31, definitivt förlorat 40 byte i ett block. Så detta är ett Valgrind fel. Detta är att säga att någonstans i din kod, du har en fördelning som är 40 byte stort så du malloced 40 bytes, och du aldrig befriade den. Troligtvis behöver du bara att hitta några minnesläcka, och hitta var du vill befria denna minnesblock. 

Och fråga 32, ogiltig skrivning av storlek 4. Återigen är detta en Valgrind fel. Detta behöver inte göra med minnesläckor nu. Detta är, de flesta likely-- jag menar, det är någon form av ogiltiga minnes rättigheter. Och troligtvis är detta en del typ av buffertspill. Där du har en matris, kanske ett heltal array, och låt oss säga att det är av storlek 5, och du försöka röra array fäste 5. Så om du försöker skriva till den värde, det är inte en bit av minne att du faktiskt har tillgång till, och så du kommer att få detta fel, säger ogiltig skrivning av storlek 4. Valgrind kommer att känna igen dig är försökte röra minnet olämpligt. 

Och det är det för quiz0. Jag är Rob Bowden, och detta är CS50.