Tenta Flashcards
(41 cards)
Hur många jämförelser behövs i värsta fall respektive bästa fall för hitta ett element i en sorterad lista med 16 element om du använder dig av binärsökning.
Motivera kortfattat ditt svar
I bästa fall (om man har tur behövs bara en jämförelse). I värsta fall kommer det behövas 𝑙𝑜𝑔(2 nere)16 + 1 jämförelser. I binärsökning kan man I varje iteration bortse från hälften av återstående element. Efter 𝑙𝑜𝑔(2 nere )16 delningar på mitten har man endast 1 element kvar. Om man inte redan hittat elementet man söker efter behövs ytterligare 1 jämförelse.
Stämmer det att en rutin (algoritm) för att lösa ett 𝒩𝒫-fullständigt problem kan användas som subrutin för att läsa vilket problem som helst i 𝒫?
Motivera ditt svar. (2p)
Ja, eftersom en rutin för att lösa ett 𝒩𝒫 fullständigt problem kan användas som subrutin för att läsa vilket problem som helst i 𝒩𝒫 och 𝒫 är en delmängd av 𝒩𝒫
include <stdio.h></stdio.h>
Look at the following C code, what will be printed after it is executed? Motivate why the output is the one you think is. (2pt)
int addOne(int var)
{
var = var + 1;
}
int main()
{
int a = 10;
addOne(a);
addOne(a);
addOne(a);
printf(“%d “, a);
return 0;
}
The output is 10, this is because the function does change the value of a, because arguments are passed as value to functions in C, that is, their value is copied locally in the function, without modifying the variable outside the function.
include <stdio.h></stdio.h>
We change the code a little, what would be printed now? Please motivate the answer. (2 pt)
int addOne(int* var)
{
*var = *var + 1;
}
int main()
{
int a = 10;
addOne(&a);
addOne(&a);
addOne(&a);
printf(“%d “, a);
return 0;
}
In the second case the output is 13 because we pass the address of a, then the value inside the memory position is modified which survives after the execution of the function.
Full in the first column of this table placing the following different types of memory:
DRAM, EEPROM, SRAM, PROM, NVRAM, Masked ROM, Flash, EPROM
The memory types are placed in this order: SRAM, DRAM, Masked ROM, PROM, EPROM, EEPROM, Flash, NVRAM
Explain the difference between “Memory mapped I/O” and “Port mapped I/O”
Memory mapped I/O is mapped into the same address space as program memory and/or user memory, and is accessed in the same way. Memory and IO share the same address and are used in the same way.
Port mapped I/O uses a separate, dedicated address space and is accessed via a dedicated set of microprocessor instructions. IO and memory use different address spaces, when accessing memory, the programmer must specify if it’s memory or IO
You are developing the firmware for a microntroller that controls the lights of a Christmas tree.
One of the pins of the microcontroller is connected to a button, which is used to control the device. The button is connected, on one side, to the microcontroller and on the other side to the voltage supply (Vcc).
A) (2 pt)
How should you configure your pin to detect when the button is pressed? You have the following 2 options to configure:
* Direction: can be input or output
* Connection: can be direct, pulldown or pullup.
B) (2 pt)
You want your lights to fade and blink smoothly, so you program the microcontroller to emit Pulse Width Modulation (PWM) pulses on a pin to control the light intensity. The PWM pulses are controlled by a timer, which, you estimate, should tick at 1KHz so that users would not notice any flickering. Your microcontroller has a master clock of 8MHz, a prescale register of 8 bits and a compare register of 8 bits. How do you set the values for these two in order to obtain the desired frequency of 1KHz?
A)
Input and pulldown. Pulldown is needed because when the button is not pressed, the pin is floating.
B)
Both the prescaler, P, and the compare register, C, accept values between 1 and 256.
Your target is 8M / (P x C) = 1000
Which means that P x C = 8000
We can set, for example, P = 200 -> C = 8000/200 = 40
Vilka steg behövs för att ta bort första element i en dubbel-länkad lista?(2pt)
Antag att det finns minst 2 element i listan.
1. Spara undan adressen till första elementet i en temp-variabel (så att man inte tappar bort det). Dvs temp = start
2. Peka om listans start-pekare (dvs den pekare som pekar på listans första element), så att den istället pekar på listans andra element. Dvs start = temp->next, eller start = start->next
3. Låt listans andra elements prev-pekare peka på null. Dvs start->prev = null (eller temp- >next->prev = null
4. Avallokera minnet för det element som tagits bort. Dvs det element som ligger i temp-variabeln
Vid sortering av en lista är basoperation att jämföra två element.
a. Vad har algoritmen bubble sort för tidskomplexitet? Använd 𝜃-notation. (1pt)
b. Hur många basoperationer behövs (alltid) för att sortera en lista med 10 element med hjälp av bubble sort? (1pt)
a. Bubble sort har tidskomplexiteten 𝜃(𝑛2).
b. Det behövs 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 𝑛∙(𝑛−1)/ 2 = 45 jämförelser (basoperationer)
Är följande binära sökträd balanserat? Motivera kortfattat ditt svar. (1pt) (20231108 fråga 5)
Trädet är inte balanserat. Vänster subträd till noden med värdet 9 har höjden 2, medans höger subträd till samma nod har höjden 0.
Lägg in en nod med värde 10 i sökträdet i trädet ovan, och visa hur trädet ser ut efteråt. Är trädet balanserat? Motivera kortfattat ditt svar.(2pt) (20231108 fråga 5)
Trädet är balanserat då höjden på vänster och höger subträd inte skiljer sig med mer än 1 för någon nod i trädet
What is the size of an integer in C?
How can I choose a specific size (for example 8 bits) for an integer?
The size of an integer depends on the environment, including compiler, CPU architecture and used libraries.
In C99 you can import inttypes.h and use specific defines for specific sizes (fixed-width integer types)
Describe the steps needed to compile a piece of code from source code to executable, in C
- Preprocessing: performs simple text modification.
- Compilation: generates assembler code from source code.
- Assembly: generates machine instructions from assembler code.
- Linking: links all “modules” together into one executable.
A peripheral is connected to a microcontroller using the I2C protocol. In order to activate the peripheral, the microcontroller needs to write the content of a register, the address of which is specified in one byte (for example 00101010), with a specific 1 byte content (for example 10011001). The I2C address of the peripheral is 00110011.
With the help of the pictures below, describe the sequence of bits sent by the microcontroller to the peripheral (20231108 fråga 8)
The microcontroller sends:
- Start signal (SDA->low SCL->high)
- Address of the peripheral (00110011)
- Write bit
- ACK by receiver
- Register address (00101010)
- ACK by receiver
- Value (10011001)
- ACK by receiver
- Stop signal (SDA->high SCL->high)
What are the advantages and disadvantages of using “Direct conversion” versus “Successive approximation” in Digital to Anaologue Conversion.
Direct conversion is almost instantaneous but requires an exponentially higher number of comparators in relation to the number of bits, making the circuit more expensive. Successive approximation, on the other hand, requires linearly higher time for number of bits used, the circuit is smaller but slower
List the 5 views of the 4+1 view model.
Just listing the names correctly is enough for 1 point.
- The logical view. It shows the key abstractions in the system as objects or object classes “code structure”. It focuses on the functionality.
- The process view shows how, at run-time, the system is composed of interacting processes
“running code”. It focuses on concurrency and distribution. - The implementation/development view shows how the software is decomposed for
development “who does what”. It focuses on the on the software development
environment. - The physical/deployment view shows the system hardware and how software processes are
distributed across the processors in the system “things you can touch”. - All views are related using use cases or scenarios. This view shows how the elements in the
four views work together in relation to how they are used externally, from people or
machines.
Vilka steg behöver du genomföra för att lägga in ett element i mitten av en array? Antag att det finns plats att lägga in minst ett element i arrayen och att det redan finns några element i arrayen. Vi vill inte att ni skriver pseudokod, utan det räcker med en konceptuell beskrivning av vad som behöver göras. (2pt)
- Ta reda på vilken plats det nya elementet skall stoppas in. Antag att det är index i.
- Flytta/kopiera alla element som ligger på plats i eller senare. ett steg “bakåt”.
- Lägg in det nya elementet på plats i.
Sortera följande lista med 16 element med hjälp av algoritmen mergesort.
8, 7, 16, 2, 14, 25, 23, 11
Är detta värsta-fallet för mergesort, det vill säga det fall där sortering av 8 element kräver maximalt antal jämförelser? Motivera kortfattat ditt svar.
Om det inte är värsta-fallet, skapa ett värsta-fall med samma värden som i listan ovan
Detta är inte värstafallet för mergesort då värsta-fallet kräveratt största och näst största värdet tillhör olika listor i varje merge-iteration där listorna har mer än 1 element vardera. Om man byter plats på 25 och 16 i den ursprungliga listan skulle man ha ett värsta-fall. (andra halvan på 20231218 fråga 4)
Den här frågan testar din kunskap om tillståndsmaskiner.
a. Vilka tre ”komponenter” ingår i en finit tillståndsmaskin (Eng: Finite State Machine)? (1p)
b. Vad är en Mealy-Moore maskin? (1pt)
a. Tillstånd, överföringar mellan tillstånd och villkor för överföringar.
b. I en Moore-maskin körs kod i tillstånden medans kod körs övergången mellan tillstånd i en Mealy maskin. En Mealy-Moore-maskin är en kombination av dem båda.
Describe the way bootloading works on an ESP32. Describe each step including first and second stage bootloaders.
First-stage bootloader: configures the access to the external flash memory and, if required, stores on it new data coming from the serial/USB port. Once finished, it accesses the flash memory (at address 0x1000) and loads and executes the second-stage bootloader.
Second-stage bootloader: reads the partition table at address 0x8000 and searches
for app partitions. It decides which application must be executed based on the content of the otadata partition: if this partition is empty or doesn’t exist, the bootloaded executes the application stored in the factory partition.
This allows to implement an over-the-air (OTA) application update process: the application code downloads the new version of your application (e.g. from web) and stores it in a new app partition.
Once the upload is completed, the id of the partition is saved in otadata and the chip is rebooted; the bootloader will execute the new version
a) What happens when a function is declared with the keyword “extern” in C? (1pt)
b) What happens when a variable is declared with the keyword “extern” in C? (1pt)
a) Nothing particular. An extern function is a function that is defined somewhere else (in another C file). Anytime a function is declared, it is by default extern (even if one doesn’t use the extern keyword). In fact, functions are always global unless declared static.
b) A variable declared as extern in a module (c-file) means that the variable is defined in another module. The memory space is thus reserved in another module, but the compiler knows the type even though it does not reserve any memory space. The variable is implicitly global.
Merge är den grundläggande operationen i algoritmen Mergesort, och den används för att “sammanfoga” två sorterade listor till en sorterad lista. I värsta fall krävs det 2𝑛 − 1 jämförelser för att slå samman två sorterade listor som innehåller 𝑛 element vardera till en sorterad lista med 2𝑛 element. Förklara när detta “värstafall” inträffar och ge ditt eget exempel som illustrerar detta fall.
Värstafallet inträffar när det största elementet och det näst största elementet av de två listorna inte finns i samma lista.
Till exempel innehåller den första listan värdena 1, 2, 3, 7 och den andra listan innehåller värdena 4, 5, 6, 8
Hur visar man att ett problem 𝑃 är 𝒩𝒫-fullständigt (Eng: 𝒩𝒫 complete)? (2p)
Tips: Man behöver göra två saker.
- Visa att 𝑃 är i 𝒩𝒫
- Identifiera något annat problem 𝑃’ som man vet är 𝒩𝒫-fullständigt, och visa att 𝑃’ kan bli polynomiskt reducerat till 𝑃.
Describe the use of the stack and the heap memory in C. (2pt)
Hints: How and when they are allocated? What do they contain?
Stack memory is used to allocate temporary memory when a function is called. Each time the function is called, the stack is allocated a piece of memory needed to store a copy of the arguments, local variables and the return address.
Heap memory is allocated manually by the programmer. It is used for variables the life of which is limited in time (otherwise they would be allocated on the static memory) and need to survive after the execution of a function.
